On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops
Original language description
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.
Czech name
O čistých zásobníkových automatech, které provádí úplný zásobníkový pop
Czech description
Článek zavádí a studuje čisté zásobníkové automaty, které vymazávají symboly ze zásobníků pouze provedením úplného zásobníkového popu. Během této operace se celý zásobník porovná s prefixem vstupního řetězce a když se shodují, tak je celý zásobník vyprázdněn a čtecí hlava se na vstupu posune za tento řetězec. Článek dokazuje, že tyto automaty definují nekonečnou hierarchii jazykových tříd. Rovněž je studován případ, kdy automat může svoje zásobníky spojovat a vytvářet nové zásobníky.<br>
Classification
Type
D - Article in proceedings
CEP classification
BD - Information theory
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F07%2F0005" target="_blank" >GA201/07/0005: Multi-information technologies: Theory, models, and methods</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
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
Article name in the collection
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
—
Number of pages
12
Pages from-to
—
Publisher name
Computer and Automation Research Institute, Hungarian Academy of Sciences
Place of publication
Balatonfured
Event location
Balatonfured
Event date
May 27, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—