COLLAPSING WORDS: A PROGRESS REPORT

DOI10.1142/S0129054106003966zbMath1103.68063OpenAlexW1973036616MaRDI QIDQ5483371

I. V. Petrov, D. S. Ananichev, Mikhail V. Volkov

Publication date: 14 August 2006

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054106003966

zbMATH Keywords

deterministic finite automatonidentity checking problem\(n\)-collapsing word\(n\)-compressing word

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees ⋮ An algorithm for recognition of \(n\)-collapsing words

Cites Work

• An extremal problem for two families of sets
• Identities in full transformation semigroups
• Image reducing words and subgroups of free groups.
• Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands
• Results on the equivalence problem for finite groups.
• WORDS GUARANTEEING MINIMUM IMAGE
• PROFINITE IDENTITIES FOR FINITE SEMIGROUPS WHOSE SUBGROUPS BELONG TO A GIVEN PSEUDOVARIETY
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM

This page was built for publication: COLLAPSING WORDS: A PROGRESS REPORT