Collapsing words, permutation conditions and coherent colorings of trees

DOI10.1016/j.tcs.2009.01.038zbMath1166.68024OpenAlexW1996123976MaRDI QIDQ1019195

Andrzej P. Kisielewicz, A. Cherubini Spoletini

Publication date: 28 May 2009

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

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

zbMATH Keywords

permutationcoloringNP-complete problemdeterministic finite automaton\(n\)-collapsing word

Mathematics Subject Classification ID

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

Related Items (1)

Recognizing 3-collapsing words over a binary alphabet

Cites Work

• Image reducing words and subgroups of free groups.
• An algorithm for recognition of \(n\)-collapsing words
• WORDS GUARANTEEING MINIMUM IMAGE
• Developments in Language Theory
• Developments in Language Theory
• A Combinatorial Approach to Collapsing Words
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Collapsing words, permutation conditions and coherent colorings of trees