Height-Deterministic Pushdown Automata

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F07%3A00022893" target="_blank" >RIV/00216224:14330/07:00022893 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Height-Deterministic Pushdown Automata
Original language description
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.
Czech name
—
Czech description
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07)
ISBN
978-3-540-74455-9
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
—
Publisher name
Springer-Verlag
Place of publication
Netherlands
Event location
Český Krumlov
Event date
Jan 1, 2007
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)