A Reduction of Finitely Expandable Deep Pushdown Automata

Lucie Dvořáková; Alexander Meduna

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

Download full text

PDF

print cite

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.

Keywords

Finite Expandability, Reduction, Non- Input Pushdown Symbols, Deep Pushown Automata

References

Download 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

DOI: https://doi.org/10.4467/20838476SI.17.005.8151

Article type: Original scientific article

Authors

Lucie Dvořáková

Brno University of Technology Faculty of Information Technology Božetěchova 2, 612 66 Brno, Czech Republic

Alexander Meduna

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 4.0

Percentage share of authors:

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

Alexander Meduna (Author) - 50%

Article corrections:

Publication languages:

English

View count: 2718

Number of downloads: 1412

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

Download xml