Complexity of problems of commutative grammars

DOI10.2168/LMCS-11(1:9)2015MaRDI QIDQ5246714zbMATH OpenOpenAlexFDO

Authors Eryk Kopczyński

Publication date 22 April 2015

Published in Logical Methods in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

commutative grammarequivalenceEuler theoremfixed alphabetmembershipParikh image

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)

Abstract: We consider commutative regular and context-free grammars, or, in other words, Parikh images of regular and context-free languages. By using linear algebra and a branching analog of the classic Euler theorem, we show that, under an assumption that the terminal alphabet is fixed, the membership problem for regular grammars (given v in binary and a regular commutative grammar G, does G generate v?) is P, and that the equivalence problem for context free grammars (do G_1 and G_2 generate the same language?) is in $mathrmP{i}_2^P$.

Recommendations

• The complexity of equivalence problems for commutative grammars
• Commutative grammars: The complexity of uniform word problems
• Tightening the complexity of equivalence problems for commutative grammars
• On the commutative equivalence of context-free languages
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete

Cited in

(28)

• Decidability problems in grammar systems
• On the commutative equivalence of context-free languages
• Problems on finite automata and the exponential time hypothesis
• Complexity of two-dimensional rank-reducing grammars
• Characterization and complexity results on jumping finite automata
• Context-free commutative grammars with integer counters and resets
• Problems on finite automata and the exponential time hypothesis
• A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing
• Complexity results for prefix grammars
• Commutative grammars: The complexity of uniform word problems
• The complexity of equivalence problems for commutative grammars
• scientific article; zbMATH DE number 1257079 (Why is no real title available?)
• Tightening the complexity of equivalence problems for commutative grammars
• Counting problems for Parikh images
• Automata for unordered trees
• Operational state complexity and decidability of jumping finite automata
• On the complexity of decidable cases of the commutation problem of languages
• scientific article; zbMATH DE number 3393744 (Why is no real title available?)
• A COMPLEX MEASURE FOR LINEAR GRAMMARS
• Decidability of right one-way jumping finite automata
• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
• On the Commutative Equivalence of Algebraic Formal Series and Languages
• On the multiplicity equivalence problem for context-free grammars
• Geometric decision procedures and the VC dimension of linear arithmetic theories
• Jumping automata over infinite words
• Monus semantics in vector addition systems with states
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• Parallel complexity of the regular code problem

This page was built for publication: Complexity of problems of commutative grammars

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