Tightening the complexity of equivalence problems for commutative grammars

DOI10.4230/LIPICS.STACS.2016.41MaRDI QIDQ4601893zbMATH OpenFDO

Authors Christoph Haase, Piotr Hofman

Publication date 24 January 2018

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

zbMATH Keywords

commutative grammarslanguage equivalencePetri netsPresburger arithmeticsemi-linear sets

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• The complexity of equivalence problems for commutative grammars
• Complexity of problems of commutative grammars
• On the commutative equivalence of context-free languages
• Commutative grammars: The complexity of uniform word problems
• On the complexity of decidable cases of the commutation problem of languages

Cited in

(17)

• A note on the equivalence and complexity of linear grammars
• Problems on finite automata and the exponential time hypothesis
• Decidability and complexity for quiescent consistency and its variations
• A type checking algorithm for concurrent object protocols
• Context-free commutative grammars with integer counters and resets
• Problems on finite automata and the exponential time hypothesis
• Commutative grammars: The complexity of uniform word problems
• scientific article; zbMATH DE number 4155910 (Why is no real title available?)
• The complexity of equivalence problems for commutative grammars
• scientific article; zbMATH DE number 1839444 (Why is no real title available?)
• Counting problems for Parikh images
• scientific article; zbMATH DE number 7204945 (Why is no real title available?)
• Complexity of problems of commutative grammars
• scientific article; zbMATH DE number 3393744 (Why is no real title available?)
• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
• On the complexity of reasoning in Kleene algebra with commutativity conditions
• Algorithmic complexity of theories with Kleene iteration

This page was built for publication: Tightening the complexity of equivalence problems for commutative grammars

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