On Simon's congruence closure of a string

DOI10.1016/j.tcs.2023.114078zbMath1520.68059MaRDI QIDQ6093575

Yo-Sub Han, Sung-Min Kim, Sang-Ki Ko, Kai Salomaa

Publication date: 7 September 2023

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

zbMATH Keywords

finite automatastate complexityshortlex normal formsSimon's congruence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithms on strings (68W32)

Related Items (1)

Simon's congruence pattern matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• State complexity of permutation and related decision problems on alphabetical pattern constraints
• State complexity of permutation on finite languages over a binary alphabet
• On the index of Simon's congruence for piecewise testability
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
• The binomial equivalence classes of finite words
• Scattered Factor-Universality of Words
• On the Simon's congruence neighborhood of languages
• Reconstructing Words from Right-Bounded-Block Words

This page was built for publication: On Simon's congruence closure of a string