State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
From MaRDI portal
Publication:6070752
Cites work
- A generalization of the Schützenberger product of finite monoids
- A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
- A survey on operational state complexity
- Bounded Algol-Like Languages
- Classification of finite monoids: the language approach
- Classifying regular events in symbolic logic
- Complexity of problems of commutative grammars
- Complexity of universality and related problems for partially ordered NFAs
- CONCUR 2004 - Concurrency Theory
- Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
- Counter machines and verification problems.
- Descriptional and computational complexity of finite automata -- a survey
- Dot-depth of star-free events
- Efficiency of automata in semi-commutation verification techniques
- Generic results for concatenation hierarchies
- Green's relations and their use in automata theory
- scientific article; zbMATH DE number 3131080 (Why is no real title available?)
- 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 2038747 (Why is no real title available?)
- scientific article; zbMATH DE number 1759611 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 2087227 (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?)
- Integer vector addition systems with states
- Intersection and union of regular languages and state complexity
- Introduction to algorithms.
- Languages of R-trivial monoids
- Minimal NFA Problems are Hard
- On Context-Free Languages
- On finite monoids having only trivial subgroups
- On the structure of semigroups
- Operational State Complexity under Parikh Equivalence
- Partially ordered automata and piecewise testability
- Permutation rewriting and algorithmic verification
- Regular languages and partial commutations
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Semilinearity of families of languages
- State complexity bounds for the commutative closure of group languages
- State complexity of permutation and related decision problems on alphabetical pattern constraints
- State complexity of permutation on finite languages over a binary alphabet
- The complexity of equivalence problems for commutative grammars
- The equivalence problem for deterministic pushdown automata is decidable
- The inclusion problem for simple languages
- The state complexities of some basic operations on regular languages
- Tightening the complexity of equivalence problems for commutative grammars
Cited in
(2)
This page was built for publication: State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6070752)
