A note on limited pushdown alphabets in stateless deterministic pushdown automata
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A note on limited pushdown alphabets in stateless deterministic pushdown automata
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
A note on limited pushdown alphabets in stateless deterministic pushdown automata
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GPP202%2F11%2FP028" target="_blank" >GPP202/11/P028: Decentralizované a koordinační supervizní řízení</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
International Journal of Foundations of Computer Science
ISSN
0129-0541
e-ISSN
—
Svazek periodika
24
Číslo periodika v rámci svazku
3
Stát vydavatele periodika
SG - Singapurská republika
Počet stran výsledku
10
Strana od-do
319-328
Kód UT WoS článku
000321428600002
EID výsledku v databázi Scopus
—