Detail publikace

A Reduction of Finitely Expandable Deep Pushdown Automata

CHARVÁT, L.; MEDUNA, A. A Reduction of Finitely Expandable Deep Pushdown Automata. Schedae Informaticae, 2018, vol. 2017, no. 26, p. 61-68. ISSN: 0860-0295.
Název česky
Redukce konečně expandovatelných hlubokých zásobníkových automatů
Typ
článek v časopise
Jazyk
anglicky
Autoři
Charvát Lucie, Ing.
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
URL
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
2018
Strany
61–68
Časopis
Schedae Informaticae, roč. 2017, č. 26, ISSN 0860-0295
DOI
10.4467/20838476SI.17.005.8151
EID Scopus
2-s2.0-85057858123
BibTeX 
@article{BUT157232,
  author="Lucie {Charvát} and Alexandr {Meduna}",
  title="A Reduction of Finitely Expandable Deep Pushdown Automata",
  journal="Schedae Informaticae",
  year="2018",
  volume="2017",
  number="26",
  pages="61--68",
  doi="10.4467/20838476SI.17.005.8151",
  issn="0860-0295",
  url="http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/"
}
Nahoru