Detail publikace

Regulated Nondeterminism in PDAs: The Non-Regular Case

MASOPUST, T. Regulated Nondeterminism in PDAs: The Non-Regular Case. Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA). books@ocg.at Band 256. Wroclaw: Austrian Computer Society, 2009. p. 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
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Klíčová slova

Pushdown automata, regulation, computational power, descriptional complexity.

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
ISBN
978-3-85403-256-4
Vydavatel
Austrian Computer Society
Místo
Wroclaw
BibTeX 
@inproceedings{BUT33731,
  author="Tomáš {Masopust}",
  title="Regulated Nondeterminism in PDAs: The Non-Regular Case",
  booktitle="Proceedings of Workshop on Non-Classical Models of Automata and Applications (NCMA)",
  year="2009",
  series="books@ocg.at Band 256",
  pages="181--194",
  publisher="Austrian Computer Society",
  address="Wroclaw",
  isbn="978-3-85403-256-4"
}
Nahoru