Článek ve sborníku konference

 
Masopust, T.: Regulated Nondeterminism in PDAs: The Non-Regular Case, In: Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA), Wroclaw, PL, ocg, 2009, s. 181-194, ISBN 978-3-85403-256-4
Jazyk publikace:angličtina
Název publikace:Regulated Nondeterminism in PDAs: The Non-Regular Case
Název (cs):Řízený nedeterminismus v zásobníkových automatech: Neregulární případ
Strany:181-194
Sborník:Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)
Konference:Workshop on Non-Classical Models of Automata and Applications (NCMA)
Řada knih:books@ocg.at Band 256
Místo vydání:Wroclaw, PL
Rok:2009
ISBN:978-3-85403-256-4
Vydavatel:Osterreichische Computer Gesellschaft
Klíčová slova
Pushdown automata, regulation, computational power, descriptional complexity.
Anotace
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.
BibTeX:
@INPROCEEDINGS{
   author = {Tomáš 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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=8977}
}