State complexity of permutation and related decision problems on alphabetical pattern constraints

DOI10.1007/978-3-030-79121-6_10MaRDI QIDQ2117669zbMATH OpenOpenAlexFDO

Authors Stefan Hoffmann

Publication date 22 March 2022

Full work available at URL https://arxiv.org/abs/2006.15178

zbMATH Keywords

finite automatastate complexityinclusion problemcommutative closurealphabetic pattern constraint language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
• State complexity of permutation on finite languages over a binary alphabet
• The state complexity of permutations on finite languages over binary alphabets
• State complexity of projection on languages recognized by permutation automata and commuting letters
• scientific article; zbMATH DE number 4053621
• On exact algorithms for the permutation CSP
• On the permutation complexity of the Cantor-like sequences
• The computational complexity of recognizing permutation functions
• The computational complexity of recognizing permutation functions
• Algebraic and combinatorial tools for state complexity: application to the star-xor problem

Cites work

• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 2087227 (Why is no real title available?)
• scientific article; zbMATH DE number 7350780 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• A generalization of the Schützenberger product of finite monoids
• A survey on operational state complexity
• CONCUR 2004 - Concurrency Theory
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Complexity of universality and related problems for partially ordered NFAs
• Dot-depth of star-free events
• Generic results for concatenation hierarchies
• Green's relations and their use in automata theory
• Languages of R-trivial monoids
• On finite monoids having only trivial subgroups
• On the structure of semigroups
• Permutation rewriting and algorithmic verification
• Regular languages and partial commutations
• State complexity bounds for the commutative closure of group languages
• State complexity of permutation on finite languages over a binary alphabet
• The dot-depth hierarchy, 45 years later
• The state complexities of some basic operations on regular languages
• The state complexity of permutations on finite languages over binary alphabets

Cited in

(4)

• State complexity bounds for the commutative closure of group languages
• On Simon's congruence closure of a string
• On Simon's congruence closure of a string
• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs

This page was built for publication: State complexity of permutation and related decision problems on alphabetical pattern constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117669)