Remarks on Separating Words

DOI10.1007/978-3-642-22600-7_12zbMath1341.68087arXiv1103.4513OpenAlexW1938663315WikidataQ56483393 ScholiaQ56483393MaRDI QIDQ5200088

Sarah Eisenstat, Erik D. Demaine, David A. Wilson, Jeffrey O. Shallit

Publication date: 29 July 2011

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1103.4513

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Variations of the separating words problem ⋮ Lower bounds on words separation: are there short identities in transformation semigroups? ⋮ On the gap between separating words and separating their reversals ⋮ On a Conjecture by Christian Choffrut ⋮ Separating the Words of a Language by Counting Factors ⋮ Unnamed Item ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ New Results on Vector and Homing Vector Automata ⋮ Looking for Pairs that Hard to Separate: A Quantum Approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unary finite automata vs. arithmetic progressions
• Finite automata and unary languages
• Separating strings with small automata
• Equivalence problem of non-deterministic finite automata
• Automaticity. I: Properties of a measure of descriptional complexity
• Magic numbers in the state hierarchy of finite automata
• A Second Course in Formal Languages and Automata Theory
• Identical Relations in Symmetric Groups and Separating Words with Reversible Automata
• Separating words with machines and groups