Article

Deterministic Pushdown Automata and Unary Languages

Author:

Giovanni PighizziniAuthors Info & Claims

CIAA '08: Proceedings of the 13th international conference on Implementation and Applications of Automata

Pages 232 - 241

https://doi.org/10.1007/978-3-540-70844-5_24

Published: 21 July 2008 Publication History

Abstract

The simulation of deterministic pushdown automata defined over a one letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be simulated by a deterministic finite automaton with a number of states which is exponential in s . We prove that this simulation is tight. Furthermore, its cost cannot be reduced even if it is performed by a two-way nondeterministic automaton. We also prove that there are unary languages for which deterministic pushdown automata cannot be exponentially more succinct than finite automata. In order to state this result, we investigate the conversion of deterministic pushdown automata into context-free grammars. We prove that in the unary case the number of variables in the resulting grammar is strictly lower than the number of variables needed in the case of nonunary alphabets.

References

[1]

Althöfer, I.: Tight lower bounds for the length of word chains. Information Processing Letters 34, 275-276 (1990).

[2]

Berstel, J., Carton, O.: On the complexity of Hopcroft's State Minimization Algorithm. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 35-44. Springer, Heidelberg (2005).

[3]

de Bruijn, N.: A combinatorial problem. Proc. Kon. Nederl. Akad. Wetensch 49, 758-764 (1946).

[4]

Domaratzki, M., Pighizzini, G., Shallit, J.: Simulating finite automata with context-free grammars. Information Processing Letters 84, 339-344 (2002).

[5]

Ginsburg, S., Greibach, S.: Deterministic context-free languages. Information and Control 9, 563-582 (1966).

[6]

Ginsburg, S., Rice, H.: Two families of languages related to ALGOL. Journal of the ACM 9, 350-371 (1962).

[7]

Goldstine, J., Price, J., Wotschke, D.: A pushdown automaton or a context-free grammar - Which is more economical? Theoretical Computer Science 18, 33-40 (1982).

[8]

Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Reading (1978).

[9]

Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979).

[10]

Knuth, D.: On the translation of languages from left to right. Information and Control 8, 607-639 (1965).

[11]

Mereghetti, C., Pighizzini, G.: Two-way automata simulations and unary languages. J. Aut. Lang. Combin. 5, 287-300 (2000).

[12]

Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM J. Comput. 30, 1976-1992 (2001).

[13]

Meyer, A., Fischer, M.: Economy of description by automata, grammars, and formal systems. In: Proc. 12th Ann. IEEE Symp. on Switching and Automata Theory, pp. 188-191 (1971).

[14]

Pighizzini, G., Shallit, J., Wang, M.-W.: Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. Journal of Computer and System Sciences 65, 393-414 (2002).

[15]

Sénizergues, G.: The equivalence problem for deterministic pushdown automata is decidable. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 671-682. Springer, Heidelberg (1997).

[16]

Stearns, R.: A regularity test for pushdown machines. Information and Control 11, 323-340 (1967).

[17]

Valiant, L.: Regularity and related problems for deterministic pushdown automata. Journal of the ACM 22, 1-10 (1975).

Cited By

Holzer MKutrib M(2010)Descriptional complexity of (un)ambiguous finite state machines and pushdown automataProceedings of the 4th international conference on Reachability problems10.5555/1881552.1881553(1-23)Online publication date: 28-Aug-2010
https://dl.acm.org/doi/10.5555/1881552.1881553

Deterministic Pushdown Automata and Unary Languages
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Efficient determinization of visibly and height-deterministic pushdown automata

New algorithms for the determinization of nondeterministic visibly and nondeterministic real-time height-deterministic pushdown automata are presented. The algorithms improve the results of existing algorithms. They construct only accessible states and ...
Flip-pushdown automata: nondeterminism is better than determinism
DLT'03: Proceedings of the 7th international conference on Developments in language theory

Flip-pushdown automata are pushdown automata with the additional ability to flip or reverse its pushdown. We investigate deterministic and nondeterministic flip-pushdown automata accepting by final state or empty pushdown. In particular, for ...
Alternating automata and a temporal fixpoint calculus for visibly pushdown languages
CONCUR'07: Proceedings of the 18th international conference on Concurrency Theory

We investigate various classes of alternating automata for visibly pushdown languages (VPL) over infinite words. First, we show that alternating visibly pushdown automata (AVPA) are exactly as expressive as their nondeterministic counterpart (NVPA) but ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CIAA '08: Proceedings of the 13th international conference on Implementation and Applications of Automata

July 2008

287 pages

ISBN:9783540708438

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 July 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Holzer MKutrib M(2010)Descriptional complexity of (un)ambiguous finite state machines and pushdown automataProceedings of the 4th international conference on Reachability problems10.5555/1881552.1881553(1-23)Online publication date: 28-Aug-2010
https://dl.acm.org/doi/10.5555/1881552.1881553

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents