Detail publikace

An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets

MEDUNA Alexander, VRÁBEL Lukáš a ZEMEK Petr. An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets. In: DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science, roč. 7386. Braga: Springer Verlag, 2012, s. 236-243. ISBN 978-3-642-31622-7. ISSN 0302-9743. Dostupné z: http://www.springerlink.com/content/071345778vgw67tm/
Název česky
Nekonečná hierarchie jazykových tříd vyplývající z bezstavových zásobníkových automatů s omezenými zásobníkovými abecedami
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Vrábel Lukáš, Ing. (UIFS FIT VUT)
Zemek Petr, Ing. (UIFS FIT VUT)
URL
Klíčová slova

bezstavové zásobníkové automaty, omezené zásobníkové abecedy, generativní síla, nekončená hierarchie jazykových tříd

Abstrakt

Jak již jejich název napovídá, bezstavové zásobníkové automaty nemají stavy. Důsledkem je, že každý jejich výpočetní krok závisí pouze na aktuálně čteném symbolu a vrcholem zásobníku. V tomto článku diskutujeme bezstavové zásobníkové automaty jejichž zásobníková abeceda je omezená kladným číslem. Ustavujeme nekonečnou hierarchii jazykových tříd vyplývající z bezstavových zásobníkových automatů s omezenými zásobníkovými abecedami. Analogický výsledek je dokázán pro bezstavové deterministické zásobníkové automaty a bezstavové zásobníkové automaty pracující v reálném čase. V závěru článku je zmíněn otevřený problém.

Rok
2012
Strany
236-243
Časopis
Lecture Notes in Computer Science, roč. 7386, ISSN 0302-9743
Sborník
DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems
Řada
Lecture Notes in Computer Science
Konference
14th International Workshop on Descriptional Complexity of Formal Systems, Braga, PT
ISBN
978-3-642-31622-7
Vydavatel
Springer Verlag
Místo
Braga, PT
DOI
BibTeX
@INPROCEEDINGS{FITPUB9953,
   author = "Alexander Meduna and Luk\'{a}\v{s} Vr\'{a}bel and Petr Zemek",
   title = "An Infinite Hierarchy of Language Families Resulting from Stateless Pushdown Automata with Limited Pushdown Alphabets",
   pages = "236--243",
   booktitle = "DCFS'12: 14th International Workshop on Descriptional Complexity of Formal Systems",
   series = "Lecture Notes in Computer Science",
   journal = "Lecture Notes in Computer Science",
   volume = 7386,
   year = 2012,
   location = "Braga, PT",
   publisher = "Springer Verlag",
   ISBN = "978-3-642-31622-7",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-642-31623-4\_18",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9953"
}
Nahoru