Viliam Geffert ; Abuzer Yakaryilmaz - Classical Automata on Promise Problems

dmtcs:2138 - Discrete Mathematics & Theoretical Computer Science, September 16, 2015, Vol. 17 no.2 -
Classical Automata on Promise Problems

Authors: Viliam Geffert 1; Abuzer Yakaryilmaz ORCID-iD2

  • 1 Institute of Computer Science [Kosice]
  • 2 Laboratorio Nacional de Computação Cientifica [Rio de Janeiro]

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 corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Second, despite of the existing quadratic gap between Las Vegas realtime probabilistic automata and one-way deterministic automata for language recognition, we show that, by turning to promise problems, the tight gap becomes exponential. Last, we show that the situation is different for one-way probabilistic automata with two-sided bounded-error. We present a family of unary promise problems that is very easy for these machines; solvable with only two states, but the number of states in two-way alternating or any simpler automata is not limited by a constant. Moreover, we show that one-way bounded-error probabilistic automata can solve promise problems not solvable at all by any other classical model.

Volume: Vol. 17 no.2
Section: Automata, Logic and Semantics
Published on: September 16, 2015
Submitted on: October 14, 2014
Keywords: promise problems,descriptional complexity,nondeterministic automata,probabilistic automata,alternating automata,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 0903.0050
Source : ScholeXplorer IsRelatedTo DOI 10.46298/dmtcs.509
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.0903.0050
  • 0903.0050
  • 10.48550/arxiv.0903.0050
  • 10.46298/dmtcs.509
  • 10.46298/dmtcs.509
Succinctness of two-way probabilistic and quantum finite automata

Consultation statistics

This page has been seen 314 times.
This article's PDF has been downloaded 538 times.