×

Separating strings with small automata. (English) Zbl 0666.68051

A finite deterministic complete automaton separates a pair u, v of input words if the actions of u and v are different. A problem arises of bounds for the function Sep(n) defined as the minimal number k of states such that for any pair, u, v of words of length at most n over a finite alphabet A one can produce a k-state automaton separating the pair. The paper brings the best yet known upper bound, to wit, \(Sep(n)=O(n^{2/5} \log^{3/5} n)\). The author regards the estimate \(O(n^{\epsilon})\) for any positive \(\epsilon\), conjectured by Ch. Choffrut, as unlikely.
Reviewer: V.Koubek

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Goralcik, P.; Koubek, V., On discerning words by automata, (13th Internat. Colloquium on Automata, Languages and Programming. 13th Internat. Colloquium on Automata, Languages and Programming, Lecture Notes Comput. Sci., 226 (1986), Springer: Springer Berlin), 116-122 · Zbl 0594.68049
[2] Huxley, M. N., The Distribution of Prime Numbers (1972), Oxford · Zbl 0248.10030
[3] Johnson, J. H., Rational equivalence relations, (13th International Colloquium on Automata, Languages and Programming. 13th International Colloquium on Automata, Languages and Programming, Lecture Notes Comput. Sci., 226 (1986), Springer: Springer Berlin), 167-176
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.