Name
Abstract | ||
|---|---|---|
It is one of the most famous open problems to determine the minimum amount of states required by a deterministic finite automaton to distinguish a pair of strings, which was stated by Christian Choffrut more than thirty years ago.We investigate the same question for different automata models and we obtain new upper and lower bounds for some of them including alternating, ultrametric, quantum, and affine finite automata. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1142/S0129054117400032 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Alternating automaton, ultrametric automaton, quantum automaton, affine automaton, state complexity, counting problem, zero-error, nondeterminism, promise problems | Affine transformation,Discrete mathematics,Combinatorics,Upper and lower bounds,Deterministic finite automaton,Automaton,Finite-state machine,Counting problem,Ultrametric space,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
28 | 5 | 0129-0541 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksandrs Belovs | 1 | 131 | 14.50 |
| J. Andres Montoya | 2 | 12 | 6.91 |
| Abuzer Yakaryilmaz | 3 | 168 | 25.31 |