Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with alternating automata:
TR14-136 | 17th October 2014
Viliam Geffert, Abuzer Yakaryilmaz

Classical Automata on Promise Problems

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by ... more >>>

TR17-046 | 8th March 2017
Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, RĂ¼diger Reischuk

Learning Residual Alternating Automata

Residuality plays an essential role for learning finite automata.
While residual deterministic and nondeterministic
automata have been understood quite well, fundamental
questions concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman have initiated
a systematic study of residual AFAs and proposed an algorithm called AL*
-an extension of ... more >>>

ISSN 1433-8092 | Imprint