A Note on Emptiness for Alternating Finite Automata with a One-Letter Alphabet

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F07%3A00015109" target="_blank" >RIV/61989100:27240/07:00015109 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
A Note on Emptiness for Alternating Finite Automata with a One-Letter Alphabet
Original language description
We present a new proof of PSPACE-hardness of the emptiness problem for alternating finite automata with a singleton alphabet. This result was shown by Holzer (1995) who used a proof relying on a series of reductions from several papers. The new proof issimple, direct and self-contained.
Czech name
A Note on Emptiness for Alternating Finite Automata with a One-Letter Alphabet
Czech description
We present a new proof of PSPACE-hardness of the emptiness problem for alternating finite automata with a singleton alphabet. This result was shown by Holzer (1995) who used a proof relying on a series of reductions from several papers. The new proof issimple, direct and self-contained.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
<a href="/en/project/1M0567" target="_blank" >1M0567: Centre for Applied Cybernetics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)