Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Descriptional complexity of pushdown store languages

Malcher, Andreas ; Meckel, Katja ; Mereghetti, Carlo ; Palano, Beatrice


Zum Volltext im pdf-Format: Dokument 1.pdf (273 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-90853
URL: http://geb.uni-giessen.de/geb/volltexte/2012/9085/


Freie Schlagwörter (Englisch): pushdown automata , pushdown store languages , descriptional complexity , decidability questions
Universität Justus-Liebig-Universität GieĂźen
Institut: Institut fĂĽr Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 1203 / 2012
Sprache: Deutsch
Erstellungsjahr: 2012
Publikationsdatum: 23.11.2012
Kurzfassung auf Englisch: It is well known that the pushdown store language P(M) of a pushdown automaton (PDA) M — i.e., the language consisting of words occurring on the pushdown
along accepting computations of M — is a regular language. Here, we design succinct nondeterministic finite automata (NFA) accepting P(M). In detail, an upper bound on the size of an NFA for P(M) is obtained, which is quadratic in the number of states and linear in the number of pushdown symbols of M. Moreover, this upper bound is shown to be asymptotically optimal. Then, several restricted variants of PDA are considered, leading to improved constructions. In all cases, we prove the asymptotical optimality of the size of the resulting NFA. Finally, we apply our results to decidability questions related to PDA, and obtain solutions in deterministic polynomial time.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand