Separating strings with small automata
type: Item
instance of: scholarly article
title: Separating strings with small automata
zbMATH Open document ID: 0666.68051
DOI: 10.1016/0020-0190(89)90215-9
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4090805
zbMATH Keywords: finite automaton
zbMATH Keywords: rational function
zbMATH Keywords: deterministic complete automaton
author: John Michael Robson
reviewed by: Václav Koubek
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90215-9
OpenAlex ID: W2060826277
cites work: Q3725551
cites work: Q5661970
cites work: Q3746906
Recommended article: Q4347164
Recommended article: Q4939575
Recommended article: String Analysis via Automata Manipulation with Logic Circuit Representation
Recommended article: An Evaluation of Automata Algorithms for String Analysis
Recommended article: Segmenting Strings Homogeneously Via Trees
Recommended article: Q4531381
Recommended article: String graphs and separators
Recommended article: From tree automata to string automata minimization
Recommended article: The Complexity of String Partitioning
description: scientific article; zbMATH DE number 4090805