
We present new results on realtime alternating, private alternating, and
quantum alternating automaton models. Firstly, we show that the emptiness
problem for alternating onecounter automata on unary alphabets is undecidable.
Then, we present two equivalent definitions of realtime private alternating
finite automata (PAFAs). We show that the emptiness problem is undecidable for
PAFAs. Furthermore, PAFAs can recognize some nonregular unary languages,
including the unary squares language, which seems to be difficult even for some
classical counter automata with twoway input. Regarding quantum finite
automata (QFAs), we show that the emptiness problem is undecidable both for
universal QFAs on general alphabets, and for alternating QFAs with two
alternations on unary alphabets. On the other hand, the same problem is
decidable for nondeterministic QFAs on general alphabets. We also show that the
unary squares language is recognized by alternating QFAs with two alternations.

We present several new results on minimal space requirements to recognize a
nonregular language: (i) realtime nondeterministic Turing machines can
recognize a nonregular unary language within weak $\log\log n$ space, (ii)
$\log\log n$ is a tight space lower bound for accepting general nonregular
languages on weak realtime pushdown automata, (iii) there exist unary
nonregular languages accepted by realtime alternating onecounter automata
within weak $\log n$ space, (iv) there exist nonregular languages accepted by
twoway deterministic pushdown automata within strong $\log\log n$ space, and,
(v) there exist unary nonregular languages accepted by twoway onecounter
automata using quantum and classical states with middle $\log n$ space and
bounded error.

This paper proves a long standing conjecture in formal language theory. It
shows that all regular languages are ChurchRosser congruential. The class of
ChurchRosser congruential languages was introduced by McNaughton, Narendran,
and Otto in 1988. A language L is ChurchRosser congruential, if there exists a
finite confluent, and lengthreducing semiThue system S such that L is a
finite union of congruence classes modulo S. It was known that there are
deterministic linear contextfree languages which are not ChurchRosser
congruential, but on the other hand it was strongly believed that all regular
language are of this form. Actually, this paper proves a more general result.