Name
Abstract | ||
|---|---|---|
We study several classical decision problems on finite automata under the (Strong) Exponential Time Hypothesis. We focus on three types of problems: universality, equivalence, and emptiness of intersection. All these problems are known to be CoNP-hard for nondeterministic finite automata, even when restricted to unary input alphabets. A different type of problems on finite automata relates to aperiodicity and to synchronizing words. We also consider finite automata that work on commutative alphabets and those working on two-dimensional words. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.3390/a10010024 | ALGORITHMS |
Keywords | DocType | Volume |
finite automata,Exponential Time Hypothesis,universality problem,equivalence problem,emptiness of intersection | Journal | 10 |
Issue | Citations | PageRank |
1 | 2 | 0.38 |
References | Authors | |
27 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henning Fernau | 1 | 1646 | 162.68 |
| Andreas Krebs | 2 | 21 | 8.20 |