A note on limited pushdown alphabets in stateless deterministic pushdown automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00394000" target="_blank" >RIV/67985840:_____/13:00394000 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1142/S0129054113500068" target="_blank" >http://dx.doi.org/10.1142/S0129054113500068</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1142/S0129054113500068" target="_blank" >10.1142/S0129054113500068</a>
Alternative languages
Result language
angličtina
Original language name
A note on limited pushdown alphabets in stateless deterministic pushdown automata
Original language description
Recently, an infinite hierarchy of languages accepted by stateless deterministic pushdown automata has been established based on the number of pushdown symbols. However, the witness language for the n-th level of the hierarchy is over an input alphabet with 2(n-1) elements. In this paper, we improve this result by showing that a binary alphabet is sufficient to establish this hierarchy. As a consequence of our construction, we solve the open problem formulated by Meduna et al. Then we extend these results to m-state realtime deterministic pushdown automata, for all m at least 1. The existence of such a hierarchy for m-state deterministic pushdown automata is left open.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GPP202%2F11%2FP028" target="_blank" >GPP202/11/P028: Decentralized and coordination supervisory control</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
International Journal of Foundations of Computer Science
ISSN
0129-0541
e-ISSN
—
Volume of the periodical
24
Issue of the periodical within the volume
3
Country of publishing house
SG - SINGAPORE
Number of pages
10
Pages from-to
319-328
UT code for WoS article
000321428600002
EID of the result in the Scopus database
—