State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs

DOI10.1142/s0129054123430025OpenAlexW4388226636MaRDI QIDQ6070752

Stefan Hoffmann

Publication date: 24 November 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054123430025

zbMATH Keywords

finite automatastate complexityParikh equivalencecommutative closurelanguage inclusion problemalphabetical pattern constraintspartially ordered nondeterministic automata

Mathematics Subject Classification ID

Theory of computing (68Qxx) Computer science (68-XX) Semigroups (20Mxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
• Regular languages and partial commutations
• Descriptional and computational complexity of finite automata -- a survey
• Permutation rewriting and algorithmic verification
• Languages of R-trivial monoids
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Intersection and union of regular languages and state complexity
• The inclusion problem for simple languages
• The state complexities of some basic operations on regular languages
• Counter machines and verification problems.
• Complexity of universality and related problems for partially ordered NFAs
• State complexity bounds for the commutative closure of group languages
• State complexity of permutation and related decision problems on alphabetical pattern constraints
• Generic results for concatenation hierarchies
• State complexity of permutation on finite languages over a binary alphabet
• Dot-depth of star-free events
• On the structure of semigroups
• Green’s Relations and Their Use in Automata Theory
• Integer Vector Addition Systems with States
• Efficiency of automata in semi-commutation verification techniques
• The complexity of equivalence problems for commutative grammars
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Minimal NFA Problems are Hard
• The equivalence problem for deterministic pushdown automata is decidable
• Complexity of Problems of Commutative Grammars
• CONCUR 2004 - Concurrency Theory
• On finite monoids having only trivial subgroups
• Operational State Complexity under Parikh Equivalence
• Bounded Algol-Like Languages
• On Context-Free Languages
• Semilinearity of Families of Languages
• Synchronization problems in automata without non-trivial cycles
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity

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