A Reduction of Finitely Expandable Deep Pushdown Automata

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F18%3APU132281" target="_blank" >RIV/00216305:26230/18:PU132281 - isvavai.cz</a>
Result on the web
<a href="http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/" target="_blank" >http://www.ejournals.eu/Schedae-Informaticae/2017/Volume-26/art/10836/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4467/20838476SI.17.005.8151" target="_blank" >10.4467/20838476SI.17.005.8151</a>

Result language
angličtina
Original language name
A Reduction of Finitely Expandable Deep Pushdown Automata
Original language description
For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the paper demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols---$ and #, where # always appears solely as the pushdown bottom. Moreover, the paper demonstrates an infinite hierarchy of language families that follows from this main result. The paper also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages.
Czech name
—
Czech description
—

Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)