A reduction of finitely expandable deep pushdown automata

• Autorzy: Dvořáková L. , Meduna A.

Identyfikatory

DOI

10.4467/20838476SI.17.005.8151

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

deep pushdown automata; finite expandability; reduction; non-input pushdown symbols

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2017
• Tom: Vol. 26
• Strony: 61--68
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Dvořáková L.

• Brno University of Technology Faculty of Information Technology Boˇzetˇechova 2, 612 66 Brno, Czech Republic

autor

Meduna A.

• Brno University of Technology Faculty of Information Technology Boˇzetˇechova 2, 612 66 Brno, Czech Republic

Bibliografia

• [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.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).