Detail publikačního výsledku

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT, L.; MEDUNA, A.

Originální název

A Reduction of Finitely Expandable Deep Pushdown Automata

Anglický název

A Reduction of Finitely Expandable Deep Pushdown Automata

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

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 presentation 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. Moreover, the presentation  demonstrates an infinite hierarchy of language families that follows from this main result. The presentation also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages.

Anglický abstrakt

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 presentation 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. Moreover, the presentation  demonstrates an infinite hierarchy of language families that follows from this main result. The presentation also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

CHARVÁT, L.; MEDUNA, A.

Vydáno

31.12.2017

Místo

Telč

Kniha

Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017)

Edice

Electronic Proceedings in Theoretical Computer Science

Strany od

1

Strany do

1

Strany počet

1

URL

https://www.fit.vut.cz/research/publication/11521/

BibTex

@inproceedings{BUT170110,
  author="Lucie {Charvát} and Alexandr {Meduna}",
  title="A Reduction of Finitely Expandable Deep Pushdown Automata",
  booktitle="Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017)",
  year="2017",
  series="Electronic Proceedings in Theoretical Computer Science",
  pages="1--1",
  address="Telč",
  url="https://www.fit.vut.cz/research/publication/11521/"
}

Dokumenty

MEMICS17_Charvat