zbMATH — the first resource for mathematics

A note on emptiness for alternating finite automata with a one-letter alphabet. (English) Zbl 1184.68317
Summary: 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 is simple, direct and self-contained.

68Q45 Formal languages and automata
Full Text: DOI
[1] Chandra, A.K.; Kozen, D.C.; Stockmeyer, L.J., Alternation, J. ACM, 28, 1, 114-133, (1981) · Zbl 0473.68043
[2] Culik, K.; Gruska, J.; Salomaa, A., On a family of L languages resulting from systolic tree automata, Theoret. comput. sci., 23, 3, 231-242, (1983) · Zbl 0549.68081
[3] Holzer, M., On emptiness and counting for alternating finite automata, (), 88-97 · Zbl 1096.68629
[4] Jančar, P.; Kučera, A.; Moller, F.; Sawa, Z., DP lower bounds for equivalence-checking and model-checking of one-counter automata, Information and computation, 188, 1-19, (2004) · Zbl 1078.68087
[5] Jiang, T.; Ravikumar, B., A note on the space complexity of some decision problems for finite automata, Inf. process. lett., 40, 1, 25-31, (1991) · Zbl 0741.68078
[6] Monti, A.; Roncato, A., Completeness results concerning systolic tree automata and E0L languages, Inf. process. lett., 53, 1, 11-16, (1995) · Zbl 0875.68528
[7] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, Pure and applied mathematics, vol. 90, (1980), Academic Press · Zbl 0365.68072
[8] Serre, O., Parity games played on transition graphs of one-counter processes, (), 337-351 · Zbl 1180.68180
[9] Srba, J., Visibly pushdown automata: from language equivalence to simulation and bisimulation, (), 89-103 · Zbl 1225.68104
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.