Recognizing 3-collapsing words over a binary alphabet

DOI10.1016/J.TCS.2015.10.045MaRDI QIDQ288795zbMATH OpenOpenAlexFDO

Authors A. Cherubini, Andrzej Kisielewicz

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)

Recommendations

• Short 3-collapsing words over a 2-letter alphabet
• Composing short 3-compressing words on a 2-letter alphabet
• scientific article; zbMATH DE number 1948504
• Collapsing words, permutation conditions and coherent colorings of trees
• An algorithm for recognition of \(n\)-collapsing words

Cites work

• scientific article; zbMATH DE number 21739 (Why is no real title available?)
• scientific article; zbMATH DE number 1948504 (Why is no real title available?)
• scientific article; zbMATH DE number 2051185 (Why is no real title available?)
• A Combinatorial Approach to Collapsing Words
• An algorithm for recognition of \(n\)-collapsing words
• Collapsing words, permutation conditions and coherent colorings of trees
• Composing short 3-compressing words on a 2-letter alphabet
• Developments in Language Theory
• Image reducing words and subgroups of free groups.
• Synchronizing Automata and the Černý Conjecture

Cited in

(3)

• Short 3-collapsing words over a 2-letter alphabet
• Composing short 3-compressing words on a 2-letter alphabet
• The simplest binary word with only three squares

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

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