Detail publikace

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT, L.; MEDUNA, A. A Reduction of Finitely Expandable Deep Pushdown Automata. Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017). Electronic Proceedings in Theoretical Computer Science. Telč: 2017. p. 1 (1 s.).
Název česky
Redukce konečně expandovatelných hlubokých zásobníkových automatů
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Charvát Lucie, Ing.
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Klíčová slova

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

Abstrakt

Pro přirozené číslo n, n-expandovatelné hluboké zasobníkové automaty vždy obsahují maximálně n výskytů nevstupních symbolů v jejich zásobníku v průběhu jakékoli kompilace. Jako hlavní výsledek, tato práce demonstruje, že tyto automaty mají stejnou vyjadřovací sílu jako automaty s #, nacházející pouze na dně zásobníku, a jediným dalším nevstupním symbolem. Z tohoto závěru vyplývá nekonečná hierarchie jazyků přijímaných těmito automaty.

Rok
2017
Strany
1–1
Sborník
Proceedings 12th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2017)
Řada
Electronic Proceedings in Theoretical Computer Science
Místo
Telč
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/"
}
Nahoru