Remarks on separating words

DOI10.1007/978-3-642-22600-7_12MaRDI QIDQ5200088zbMATH OpenOpenAlexWikidataFDO

Authors Erik D. Demaine, Sarah Eisenstat, David A. Wilson, Jeffrey 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)

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.

Recommendations

• Separating strings with small automata
• On the gap between separating words and separating their reversals
• Publication:4939575
• Separating words with machines and groups
• Efficient separability of regular languages by subsequences and suffixes

Cites work

• A Second Course in Formal Languages and Automata Theory
• Automaticity. I: Properties of a measure of descriptional complexity
• Equivalence problem of non-deterministic finite automata
• Finite automata and unary languages
• scientific article; zbMATH DE number 3956447 (Why is no real title available?)
• scientific article; zbMATH DE number 1400022 (Why is no real title available?)
• Identical relations in symmetric groups and separating words with reversible automata
• Magic numbers in the state hierarchy of finite automata
• Separating strings with small automata
• Separating words with machines and groups
• Unary finite automata vs. arithmetic progressions

Cited in

(16)

• On the gap between separating words and separating their reversals
• Variations of the separating words problem
• A multi-parameter analysis of hard problems on deterministic finite automata
• Separating many words by counting occurrences of factors
• Lower bounds on words separation: are there short identities in transformation semigroups?
• Looking for Pairs that Hard to Separate: A Quantum Approach
• scientific article; zbMATH DE number 5896082 (Why is no real title available?)
• scientific article; zbMATH DE number 5507716 (Why is no real title available?)
• On a conjecture by Christian Choffrut
• Separating words with machines and groups
• scientific article; zbMATH DE number 1400022 (Why is no real title available?)
• Words separation and positive identities in symmetric groups
• Separating the words of a language by counting factors
• New results on vector and homing vector automata
• Separating words by occurrences of subwords
• Symbol Separation in Double Occurrence Words

This page was built for publication: Remarks on separating words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5200088)