O čistých zásobníkových automatech, které provádí úplný zásobníkový pop
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F08%3APU76706" target="_blank" >RIV/00216305:26230/08:PU76706 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Popis výsledku v původním jazyce
This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete-pushdown pops. During this operation, the entire pushdown is compared with a prefix of the input, and if they match, thepushdown is completely emptied and the input is advanced by the prefix. The paper proves that these automata define an infinite hierarchy of language families identical with the infinite hierarchy of language families resulting from right linear simplematrix grammars. If these automata are allowed to join their pushdowns and create new pushdowns, then they define another infinite hierarchy of language families according to the number of pushdowns.
Název v anglickém jazyce
On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Popis výsledku anglicky
This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete-pushdown pops. During this operation, the entire pushdown is compared with a prefix of the input, and if they match, thepushdown is completely emptied and the input is advanced by the prefix. The paper proves that these automata define an infinite hierarchy of language families identical with the infinite hierarchy of language families resulting from right linear simplematrix grammars. If these automata are allowed to join their pushdowns and create new pushdowns, then they define another infinite hierarchy of language families according to the number of pushdowns.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BD - Teorie informace
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA201%2F07%2F0005" target="_blank" >GA201/07/0005: Multiinformační technologie: Teorie, modely a metody</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2008
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 statě ve sborníku
Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings
ISBN
978-963-311-367-7
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
—
Název nakladatele
Computer and Automation Research Institute, Hungarian Academy of Sciences
Místo vydání
Balatonfured
Místo konání akce
Balatonfured
Datum konání akce
27. 5. 2008
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—