Tightening the complexity of equivalence problems for commutative grammars

DOI10.4230/LIPICS.STACS.2016.41zbMATH Open1388.68154arXiv1506.07774MaRDI QIDQ4601893FDOQ4601893

Authors: Christoph Haase, Piotr Hofman 

Publication date: 24 January 2018

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

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

zbMATH Keywords

Petri netsPresburger arithmeticlanguage equivalencesemi-linear setscommutative grammars

Mathematics Subject Classification ID

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

Cited In (16)

• A note on the equivalence and complexity of linear grammars
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of problems of commutative grammars
• Context-free commutative grammars with integer counters and resets
• On the complexity of reasoning in Kleene algebra with commutativity conditions
• Counting problems for Parikh images
• A type checking algorithm for concurrent object protocols
• Problems on finite automata and the exponential time hypothesis
• Problems on finite automata and the exponential time hypothesis
• Commutative grammars: The complexity of uniform word problems
• Decidability and complexity for quiescent consistency and its variations
• Title not available (Why is that?)
• Title not available (Why is that?)
• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
• The complexity of equivalence problems for commutative grammars

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)