Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{727702,
author = {Nowotka, Dirk and Srba, Jiří},
address = {Netherlands},
booktitle = {32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07)},
keywords = {pushdown automata - visibly pushdown laguages - height determinism},
language = {eng},
location = {Netherlands},
isbn = {978-3-540-74455-9},
pages = {125-134},
publisher = {Springer-Verlag},
title = {Height-Deterministic Pushdown Automata},
year = {2007}
}
TY - JOUR
ID - 727702
AU - Nowotka, Dirk - Srba, Jiří
PY - 2007
TI - Height-Deterministic Pushdown Automata
PB - Springer-Verlag
CY - Netherlands
SN - 9783540744559
KW - pushdown automata - visibly pushdown laguages - height determinism
N2 - We define the notion of height-deterministic pushdown automata, a model where for any given input string the stack heights during any (nondeterministic) computation on the input are a priori fixed. Different subclasses of height-deterministic pushdown automata, strictly containing the class of regular languages and still closed under boolean language operations, are considered. Several of such language classes have been described in the literature. Here, we suggest a natural and intuitive model that subsumes all the formalisms proposed so far by employing height-deterministic pushdown automata. Decidability and complexity questions are also considered.
ER -
NOWOTKA, Dirk a Jiří SRBA. Height-Deterministic Pushdown Automata. In \textit{32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07)}. Netherlands: Springer-Verlag, 2007, s.~125-134. ISBN~978-3-540-74455-9.
|
