Publication Details
On Stateless Pushdown Automata And Limited Pushdown Alphabets
stateless pushdown automata, limited pushdown alphabets, binary input alphabet, generative power, infinite hierarchy of language families
As its name suggests, a stateless pushdown automaton has no states. As a result, each of its computational steps depends only on the currently scanned symbol and the current pushdown- store top. Recently, there has been an interest in the investigation of limited pushdown alphabets. An infinite hierarchy of languages has been established based on this limitation. The proof was based on the language with growing input alphabet. This result was then improved by showing that the binary alphabet is sufficient for deterministic stateless automata. In this paper, we consider general nondeterministic stateless pushdown automata. We generalize these recent results by establishing an infinite hierarchy of language families resulting from stateless pushdown automata with limited pushdown alphabets and binary input alphabets.
@misc{BUT192885,
author="Lukáš {Vrábel}",
title="On Stateless Pushdown Automata And Limited Pushdown Alphabets",
year="2013",
pages="5",
publisher="Brno University of Technology",
url="https://www.fit.vut.cz/research/publication/10279/",
note="miscellaneous"
}