6533b871fe1ef96bd12d0d8d
RESEARCH PRODUCT
On a Conjecture by Christian Choffrut
Aleksandrs BelovsAbuzer YakaryilmazJ. Andres Montoyasubject
Discrete mathematicsFinite-state machineConjecture010102 general mathematics02 engineering and technology01 natural sciencesUpper and lower boundsAutomatonDeterministic finite automatonCounting problem0202 electrical engineering electronic engineering information engineeringComputer Science (miscellaneous)020201 artificial intelligence & image processingAffine transformation0101 mathematicsUltrametric spaceMathematicsdescription
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 | journal | country | edition | language |
|---|---|---|---|---|
| 2017-08-01 | International Journal of Foundations of Computer Science |