Tightening the complexity of equivalence problems for commutative grammars

DOI10.4230/LIPICS.STACS.2016.41MaRDI QIDQ4601893zbMATHFDO

Authors Christoph Haase, Piotr Hofman

Publication date 24 January 2018

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

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)

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

(16)

• Problems on finite automata and the exponential time hypothesis
• Problems on finite automata and the exponential time hypothesis
• Context-free commutative grammars with integer counters and resets
• scientific article; zbMATH DE number 1839444 (Why is no real title available?)
• On the complexity of reasoning in Kleene algebra with commutativity conditions
• Complexity of problems of commutative grammars
• Decidability and complexity for quiescent consistency and its variations
• scientific article; zbMATH DE number 3393744 (Why is no real title available?)
• Counting problems for Parikh images
• The complexity of equivalence problems for commutative grammars
• A note on the equivalence and complexity of linear grammars
• scientific article; zbMATH DE number 4155910 (Why is no real title available?)
• scientific article; zbMATH DE number 7204945 (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
• A type checking algorithm for concurrent object protocols
• Commutative grammars: The complexity of uniform word problems

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)