Name
Abstract | ||
|---|---|---|
We study the problem of discerning strings with deterministic finite state automata (DFAs, for short). We begin with a survey on the historical and algorithmic roots of this problem. Then, we focus on the maximun number of states that are necessary to separate two strings of a given length. We survey the most important results concerning this issue and we study the problem from the point of view of some alternative models of automata. The preliminary results concerning the last issue motivate us to formulate a conjecture stating that DFAs can separate any pair of strings by using a logarithmic number of states. We give some evidence supporting our conjecture. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/CLEI.2015.7360021 | 2015 Latin American Computing Conference (CLEI) |
Keywords | Field | DocType |
discerning string,deterministic finite state automata,DFA,logarithmic number | Discrete mathematics,Quantum finite automata,Automata theory,Nested word,Mobile automaton,Deterministic finite automaton,Finite-state machine,DFA minimization,Mathematics,ω-automaton | Conference |
ISSN | Citations | PageRank |
2381-1609 | 1 | 0.37 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abuzer Yakaryilmaz | 1 | 168 | 25.31 |
| J. Andres Montoya | 2 | 1 | 0.37 |