Remarks on separating words
arXiv:1103.4513
Abstract
The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length <= n (by accepting one and rejecting the other). In this paper we survey what is known and unknown about the problem, consider some variations, and prove several new results.
Cited by in corpus (5)
- Semigroup identities of tropical matrices through matrix ranks
- Can one quantum bit separate any pair of words with zero-error?
- Distinguishability Operations and Closures on Regular Languages
- Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?
- On the Gap Between Separating Words and Separating Their Reversals