Nearly \(k\)-universal words -- investigating a part of Simon's congruence

DOI10.1016/j.tcs.2023.114113OpenAlexW4385623536MaRDI QIDQ6073651

Annika Huch, Lukas Haschke, Pamela Fleischmann, Jonas Höfer, Dirk Nowotka, Annika Mayrock

Publication date: 18 September 2023

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

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

zbMATH Keywords

\(m\)-nearly \(k\)-universalscattered factorscattered factor universalitySimon congruence

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• On the word problem for syntactic monoids of piecewise testable languages.
• Normal forms under Simon's congruence
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• The smallest automaton recognizing the subwords of a text
• Reconstructing words from subwords in linear time
• On the index of Simon's congruence for piecewise testability
• Absent subsequences in words
• Linear work suffix array construction
• The Complexity of Some Problems on Subsequences and Supersequences
• On the distribution of the length of the longest increasing subsequence of random permutations
• The String-to-String Correction Problem
• Scattered Factor-Universality of Words
• The Height of Piecewise-Testable Languages with Applications in Logical Complexity
• Reconstructing Words from Right-Bounded-Block Words
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Nearly \(k\)-universal words -- investigating a part of Simon's congruence