2020/06/26 by Stefan Hoffmann, Hoffmann, Stefan
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q45 (Primary) 68Q19 (Secondary) #Algorithms and Data Compression #D.2.4 #DNA and Biological Computing #F.1.3 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2006.15178
openalex publication_date 2020/06/26 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We investigate the state complexity of the permutation operation, or the\ncommutative closure, on Alphabetical Pattern Constraints (APC). This class\ncorresponds to level 3/2 of the Straubing-Th 'erien Hierarchy and includes\nthe finite, the piecewise-testable, or mathcal J-trivial, and the mathcal\nR-trivial and mathcal L-trivial languages. We give a sharp state complexity\nbound expressed in terms of the longest strings in the unary projection\nlanguages of an associated finite language and which is already sharp for the\nsubclass of finite languages. Additionally, for two subclasses, we give sharp\nbounds expressed in terms of the size of a recognizing input automaton and the\nsize of the alphabet. Lastly, we investigate the inclusion and universality\nproblem on APCs up to permutational equivalence, two problems known to be\nPSPACE-complete on APCs even for fixed alphabets in general, and show them to\nbe decidable in polynomial time for fixed alphabets in this case.\n