%0 Generic %1 fleszar2010complementation %A Fleszar, Krzysztof %D 2010 %K automata multihead myown nondeterministic %T Complementation of Multihead Automata %X Since the proofs of Szelepscényi Szel87 and Immerman Imme88 it is known that nondeterministic space-bounded complexity classes are closed under complementation. Consequently this result is true for nondeterministic Turing machines bounded by logarithmic space, or equivalently for nondeterministic finite automata with two-way input heads. By utilizing the inductive counting technique Cook et al. showed that complementation holds also for LOGCFL, a complexity class that can be represented by nondeterministic finite pushdown automata bounded by polynomial time. This raises the question how the complementation of these automata is related to the increase of input heads of the complementing machine. The following results are evinced: 1. For every language L accepted by a nondeterministic finite automaton with k two-way input heads there exists a nondeterministic finite automaton with 8k+1 two-way input heads accepting the complement of L. 2. For every language L accepted by a nondeterministic pushdown automaton M with k two-way input heads working in time n^r there exists a nondeterministic pushdown automaton M\′ with 18k+5r two-way input heads accepting the complement of L in time O(n^8k+2r).

@misc{fleszar2010complementation, abstract = {Since the proofs of Szelepscényi Szel87 and Immerman Imme88 it is known that nondeterministic space-bounded complexity classes are closed under complementation. Consequently this result is true for nondeterministic Turing machines bounded by logarithmic space, or equivalently for nondeterministic finite automata with two-way input heads. By utilizing the inductive counting technique Cook et al. showed that complementation holds also for LOGCFL, a complexity class that can be represented by nondeterministic finite pushdown automata bounded by polynomial time. This raises the question how the complementation of these automata is related to the increase of input heads of the complementing machine. The following results are evinced: 1. For every language L accepted by a nondeterministic finite automaton with k two-way input heads there exists a nondeterministic finite automaton with 8k+1 two-way input heads accepting the complement of L. 2. For every language L accepted by a nondeterministic pushdown automaton M with k two-way input heads working in time n^r there exists a nondeterministic pushdown automaton M\′ with 18k+5r two-way input heads accepting the complement of L in time O(n^8k+2r).}, added-at = {2013-06-12T11:35:12.000+0200}, author = {Fleszar, Krzysztof}, biburl = {https://www.bibsonomy.org/bibtex/27a0f263239d6ab847e6da0ce26340a44/fleszark}, howpublished = {Bachelor thesis, Lehrstuhl f\"ur Informatik IV, Universit\"at W\"urzburg}, interhash = {7865c7dca904c9b82a7abb66db36185a}, intrahash = {7a0f263239d6ab847e6da0ce26340a44}, keywords = {automata multihead myown nondeterministic}, month = jul, school = {Lehrstuhl f\"ur Informatik IV, Universit\"at W\"urzburg}, timestamp = {2014-10-20T13:53:30.000+0200}, title = {Complementation of Multihead Automata}, type = {bachelor thesis}, year = 2010 }