Article3001: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Markus Krötzsch (Diskussion | Beiträge) K (Textersetzung - „Information Systems“ durch „Knowledge Systems“) |
Tomas Masopust (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
|ErsterAutorVorname=Tomáš | |||
|ErsterAutorNachname=Masopust | |ErsterAutorNachname=Masopust | ||
}} | }} | ||
{{Article | {{Article | ||
| Zeile 16: | Zeile 16: | ||
|Abstract=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 nth 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 ≥ 1. The existence of such a hierarchy for m-state deterministic pushdown automata is left open. | |Abstract=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 nth 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 ≥ 1. The existence of such a hierarchy for m-state deterministic pushdown automata is left open. | ||
|ISSN=0129-0541 | |ISSN=0129-0541 | ||
|Download=A Note on Limited Pushdown Alphabets in Stateless Deterministic Pushdown Automata.pdf | |||
|DOI Name=10.1142/S0129054113500068 | |DOI Name=10.1142/S0129054113500068 | ||
|Forschungsgruppe=Knowledge Systems | |Forschungsgruppe=Knowledge Systems | ||
}} | }} | ||
Version vom 28. Oktober 2014, 17:46 Uhr
A Note on Limited Pushdown Alphabets in Stateless Deterministic Pushdown Automata
Tomáš MasopustTomáš Masopust
Tomáš Masopust
A Note on Limited Pushdown Alphabets in Stateless Deterministic Pushdown Automata
International Journal of Foundations of Computer Science, 24(3):319-328, 2014
A Note on Limited Pushdown Alphabets in Stateless Deterministic Pushdown Automata
International Journal of Foundations of Computer Science, 24(3):319-328, 2014
- KurzfassungAbstract
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 nth 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 ≥ 1. The existence of such a hierarchy for m-state deterministic pushdown automata is left open. - Forschungsgruppe:Research Group: Knowledge SystemsKnowledge-Based Systems
@article{M2014,
author = {Tom{\'{a}}{\v{s}} Masopust},
title = {A Note on Limited Pushdown Alphabets in Stateless Deterministic
Pushdown Automata},
journal = {International Journal of Foundations of Computer Science},
volume = {24},
number = {3},
year = {2014},
pages = {319-328},
doi = {10.1142/S0129054113500068}
}
