Back to Search
Start Over
Congruences for Visibly Pushdown Languages.
- Source :
- Automata, Languages & Programming (9783540275800); 2005, p1102-1114, 13p
- Publication Year :
- 2005
-
Abstract
- We study congruences on words in order to characterize the class of visibly pushdown languages (Vpl), a subclass of context-free languages. For any language L, we define a natural congruence on words that resembles the syntactic congruence for regular languages, such that this congruence is of finite index if, and only if, L is a Vpl. We then study the problem of finding canonical minimal deterministic automata for Vpls. Though Vpls in general do not have unique minimal automata, we consider a subclass of VPAs called k-module single-entry VPAs that correspond to programs with recursive procedures without input parameters, and show that the class of well-matched Vpls do indeed have unique minimal k-module single-entry automata. We also give a polynomial time algorithm that minimizes such k-module single-entry VPAs. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540275800
- Database :
- Supplemental Index
- Journal :
- Automata, Languages & Programming (9783540275800)
- Publication Type :
- Book
- Accession number :
- 32701494
- Full Text :
- https://doi.org/10.1007/11523468_89