Descriptional Complexity of Pushdown Store Languages

被引：0

作者：

Malcher, Andreas ^{[1
]}

Meckel, Katja ^{[1
]}

Mereghetti, Carlo ^{[2
]}

Palano, Beatrice ^{[2
]}

机构：

[1] Univ Giessen, Inst Informat, Arndtstr 2, D-35392 Giessen, Germany

[2] Univ Milan, Dipartimento Informat, I-20135 Milan, Italy

来源：

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2012 | 2012年 / 7386卷

关键词：

pushdown automata; pushdown store languages; descriptional complexity; decidability questions; FINITE AUTOMATA; SPACE;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：209 / 221

页数：13

共 20 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

[Anonymous], 2010, Scientific Applications of Language Methods, DOI DOI 10.1142/97818481654580001

[3]

Autebert J.-M., 1997, Handbook of formal languages, V1, P111, DOI [10.1007/978-3-642-59136-5_3, DOI 10.1007/978-3-642-59136-5_3]

[4]

Bednarova Zuzana, 2011, Descriptional Complexity of Formal Systems. Proceedings 13th International Workshop, DCFS 2011, P80, DOI 10.1007/978-3-642-22600-7_7

[5]

Dassow Jurgen, 2011, Descriptional Complexity of Formal Systems. Proceedings 13th International Workshop, DCFS 2011, P135, DOI 10.1007/978-3-642-22600-7_11

[6] More concise representation of regular languages by automata and regular expressions [J].