Back to Search
Start Over
On a Conjecture by Christian Choffrut.
- Source :
- International Journal of Foundations of Computer Science; Aug2017, Vol. 28 Issue 5, p483-501, 19p
- Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 28
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 126798468
- Full Text :
- https://doi.org/10.1142/S0129054117400032