Detail publikace

Regulated Nondeterminism in PDAs: The Non-Regular Case

MASOPUST Tomáš. Regulated Nondeterminism in PDAs: The Non-Regular Case. In: Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA). books@ocg.at Band 256. Wroclaw: Osterreichische Computer Gesellschaft, 2009, s. 181-194. ISBN 978-3-85403-256-4.
Název česky
Řízený nedeterminismus v zásobníkových automatech: Neregulární případ
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
Abstrakt

V tomto článku jsou diskutovány zásobníkové automaty, jenž mohou provést nedeterministický krok pouze tehdy, když obsah jejich zásobníku tvoří slovo patřící do daného kotrolního jazyka. Je dokázáno, že pokud je kontrolní jazyk lineární a neregulární, pak síla takovýchto automatů je stejná jako síla Turingova stroje. Jelikož kontrolování obsahu zásobníku v každém kroku výpočtu není příliš efektivní, je rovněž ukázáno, že stačí tuto kontrolu provést pouze dvakrát během výpočtu.

Rok
2009
Strany
181-194
Sborník
Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)
Řada
books@ocg.at Band 256
Konference
Workshop on Non-Classical Models of Automata and Applications (NCMA), Wroclaw, Poland, PL
ISBN
978-3-85403-256-4
Vydavatel
Osterreichische Computer Gesellschaft
Místo
Wroclaw, PL
BibTeX 
@INPROCEEDINGS{FITPUB8977,
   author = "Tom\'{a}\v{s} Masopust",
   title = "Regulated Nondeterminism in PDAs: The Non-Regular Case",
   pages = "181--194",
   booktitle = "Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)",
   series = "books@ocg.at Band 256",
   year = 2009,
   location = "Wroclaw, PL",
   publisher = "Austrian Computer Society",
   ISBN = "978-3-85403-256-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8977"
}
Nahoru