2 citations · 2 across the 2 of their papers we have counts for
3 papers
Alternating, private alternating, and quantum alternating realtime automata
Gökalp Demirci, Mika Hirvensalo, Klaus Reinhardt +2
We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-count…
New Results on the Minimum Amount of Useful Space
Zuzana Bednárová, Viliam Geffert, Klaus Reinhardt +1
We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary lang…
Regular Languages are Church-Rosser Congruential
Volker Diekert, Manfred Kufleitner, Klaus Reinhardt +1
This paper proves a long standing conjecture in formal language theory. It shows that all regular languages are Church-Rosser congruential. The class of Church-Rosser congruential…