FAQ
logo of Jagiellonian University in Krakow

A 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.8151

Authors

,
Lucie Dvořáková
Brno University of Technology Faculty of Information Technology Božetěchova 2, 612 66 Brno, Czech Republic
All publications →
Alexander Meduna
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
All publications →

Titles

A Reduction of Finitely Expandable Deep Pushdown Automata

Abstract

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.

References

[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

Information: Schedae Informaticae, 2017, Volume 26, pp. 61 - 68

Article type: Original article

Titles:

Polish:

A Reduction of Finitely Expandable Deep Pushdown Automata

English:

A Reduction of Finitely Expandable Deep Pushdown Automata

Authors

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  licence icon

Percentage share of authors:

Lucie Dvořáková (Author) - 50%
Alexander Meduna (Author) - 50%

Article corrections:

-

Publication languages:

English

View count: 2132

Number of downloads: 1019

<p> A Reduction of Finitely Expandable Deep Pushdown Automata</p>