On the Simon's congruence neighborhood of languages

DOI10.1007/978-3-031-33264-7_14MaRDI QIDQ6067338

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

Publication date: 16 November 2023

Published in: Developments in Language Theory (Search for Journal in Brave)

zbMATH Keywords

computational complexitycongruence relationSimon's congruence\(k\)-piecewise testable languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Simon's congruence pattern matching ⋮ On Simon's congruence closure of a string

Cites Work

• Approximate matching between a context-free grammar and a finite-state automaton
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• A local algorithm for DNA sequence alignment with inversions
• On Simon's congruence closure of a string
• On the index of Simon's congruence for piecewise testability
• Relationships between nondeterministic and deterministic tape complexities
• Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
• On the Complexity of k-Piecewise Testability and the Depth of Automata
• Algorithms for approximate string matching
• Complexity of some problems from the theory of automata
• Scattered Factor-Universality of Words
• Alternative Automata Characterization of Piecewise Testable Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Simon's congruence neighborhood of languages