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

DOI10.1007/978-3-030-79121-6_10OpenAlexW3175373088MaRDI QIDQ2117669FDOQ2117669

Authors: Stefan Hoffmann 

Publication date: 22 March 2022

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

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

zbMATH Keywords

finite automatastate complexityinclusion problemcommutative closurealphabetic pattern constraint language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• The state complexities of some basic operations on regular languages
• On the structure of semigroups
• Green's relations and their use in automata theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• On finite monoids having only trivial subgroups
• Classifying regular events in symbolic logic
• Title not available (Why is that?)
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Dot-depth of star-free events
• Regular languages and partial commutations
• Title not available (Why is that?)
• Permutation rewriting and algorithmic verification
• CONCUR 2004 - Concurrency Theory
• Languages of R-trivial monoids
• Complexity of universality and related problems for partially ordered NFAs
• Generic results for concatenation hierarchies
• A survey on operational state complexity
• Title not available (Why is that?)
• The dot-depth hierarchy, 45 years later
• Title not available (Why is that?)
• State complexity bounds for the commutative closure of group languages
• State complexity of permutation on finite languages over a binary alphabet
• 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)