A note on emptiness for alternating finite automata with a one-letter alphabet

DOI10.1016/j.ipl.2007.06.006zbMath1184.68317OpenAlexW1999507562MaRDI QIDQ2380016

Petr Jančar, Zdeněk Sawa

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.06.006

zbMATH Keywords

computational complexityemptinessalternating finite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Countdown games, and simulation on (succinct) one-counter nets, On history-deterministic one-counter nets, The complexity of synchronizing Markov decision processes, Strategic reasoning with a bounded number of resources: the quest for tractability, Reachability on prefix-recognizable graphs, Unnamed Item, Optimally Resilient Strategies in Pushdown Safety Games, Model Checking FO(R) over One-Counter Processes and beyond, Bounds for synchronizing Markov decision processes

Cites Work

• Unnamed Item
• Unnamed Item
• Completeness results concerning systolic tree automata and E0L languages
• On a family of L languages resulting from systolic tree automata
• A note on the space complexity of some decision problems for finite automata
• DP lower bounds for equivalence-checking and model-checking of one-counter automata
• Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation
• Alternation
• Foundations of Software Science and Computation Structures