Recognizing 3-collapsing words over a binary alphabet

DOI10.1016/j.tcs.2015.10.045zbMath1339.68144OpenAlexW2156992022MaRDI QIDQ288795

Andrzej P. Kisielewicz, A. Cherubini Spoletini

Publication date: 27 May 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.10.045

zbMATH Keywords

\(k\)-collapsing words\(k\)-compressible automatapermutation conditions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Collapsing words, permutation conditions and coherent colorings of trees
• Image reducing words and subgroups of free groups.
• An algorithm for recognition of \(n\)-collapsing words
• Synchronizing Automata and the Černý Conjecture
• Composing short 3-compressing words on a 2 letter alphabet
• Developments in Language Theory
• A Combinatorial Approach to Collapsing Words

This page was built for publication: Recognizing 3-collapsing words over a binary alphabet