A Reduction of Finitely Expandable Deep Pushdown Automata
cytuj
pobierz pliki
RIS BIB ENDNOTEChoose format
RIS BIB ENDNOTEA Reduction of Finitely Expandable Deep Pushdown Automata
Publication date: 16.02.2018
Schedae Informaticae, 2017, Volume 26, pp. 61 - 68
https://doi.org/10.4467/20838476SI.17.005.8151Authors
A Reduction of Finitely Expandable Deep Pushdown Automata
For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the present paper demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols - $ and #, where # always appears solely as the pushdown bottom. The paper demonstrates an infinite hierarchy of language families that follows from this main result. The paper also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages. In its conclusion, the paper suggests open problems and topics for the future investigation.
[1] Kalra N., Kumar A., Fuzzy state grammar and fuzzy deep pushdown automaton, Journal of Intelligent and Fuzzy Systems, 2016, 31 (1), pp. 249–258.
[2] Kalra N., Kumar A., State grammar and deep pushdown automata for biological sequences of nucleic acids, Current Bioinformatics, 2016, 11 (4), pp. 470–479.
[3] Arratia A., Stewart I. A., Program schemes with deep pushdown storage, in: Proc. of Logic and Theory of Algorithms, CiE 2008, Vol. 5028 of Lecture Notes in Computer Science, Springer, 2008, pp. 11–21.
[4] Meduna A., Deep pushdown automata, Acta Inf., 2006, 42 (8-9), pp. 541–552.
[5] Harrison M. A., Introduction to Formal Language Theory, Addison-Wesley, 1978.
[6] Meduna A., Automata and Languages: Theory and Applications, Springer, 2000.
[7] Meduna A., Zemek P., Regulated Grammars and Automata, Springer, 2014.
[8] Leupold P., Meduna A., Finately expandable deep PDAs, in: Proc. of Automata, Formal Languages and Algebraic Systems, World Scientific, 2010, pp. 113–123.
Information: Schedae Informaticae, 2017, Volume 26, pp. 61 - 68
Article type: Original article
Titles:
A Reduction of Finitely Expandable Deep Pushdown Automata
A Reduction of Finitely Expandable Deep Pushdown Automata
Brno University of Technology Faculty of Information Technology Božetěchova 2, 612 66 Brno, Czech Republic
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
Published at: 16.02.2018
Article status: Open
Licence: CC BY-NC-ND
Percentage share of authors:
Article corrections:
-Publication languages:
EnglishView count: 2132
Number of downloads: 1019