Tightening the Complexity of Equivalence Problems for Commutative Grammars
classification
💻 cs.FL
cs.LO
keywords
equivalencecommutativegrammarslanguagelowerproblemsadditionautomata
read the original abstract
We show that the language equivalence problem for regular and context-free commutative grammars is coNEXP-complete. In addition, our lower bound immediately yields further coNEXP-completeness results for equivalence problems for communication-free Petri nets and reversal-bounded counter automata. Moreover, we improve both lower and upper bounds for language equivalence for exponent-sensitive commutative grammars.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.