An Oracle Hierarchy for Small One-Way Finite Automata
| Autor: | Christos A. Kapoutsis, Mohammad Zakzok, M. Anabtawi, Sabit Hassan |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
050101 languages & linguistics TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Finite-state machine Hierarchy (mathematics) Computer science Generalization 05 social sciences 02 engineering and technology Oracle Complement (complexity) Deterministic finite automaton Bounded function 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Nondeterministic finite automaton Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Language and Automata Theory and Applications ISBN: 9783030134341 LATA |
| DOI: | 10.1007/978-3-030-13435-8_4 |
| Popis: | We introduce a polynomial-size oracle hierarchy for one-way finite automata. In it, a problem is in level k (resp., level 0) if itself or its complement is solved by a polynomial-size nondeterministic finite automaton with access to an oracle for a problem in level \(k - 1\) (resp., by a polynomial-size deterministic finite automaton with no oracle access). This is a generalization of the polynomial-size alternating hierarchy for one-way finite automata, as previously defined using polynomial-size alternating finite automata with a bounded number of alternations; and relies on an original definition of what it means for a nondeterministic finite automaton to access an oracle, which we carefully justify. We prove that our hierarchy is strict; that every problem in level k is solved by a deterministic finite automaton of 2k-fold exponential size; and that level 1 already contains problems beyond the entire alternating hierarchy. We then identify five restrictions to our oracle-automaton, under which the oracle hierarchy is proved to coincide with the alternating one, thus providing an oracle-based characterization for it. We also show that, given all others, each of these restrictions is necessary for this characterization. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|