The complexity of equivalence problems for commutative grammars
From MaRDI portal
Publication:3736915
DOI10.1016/S0019-9958(85)80015-2zbMath0601.68048MaRDI QIDQ3736915
Publication date: 1985
Published in: Information and Control (Search for Journal in Brave)
computational complexitydecidabilityregular grammarscontext-free commutative grammarscontext-sensitive commutative grammarsinequivalence problems
Related Items
Context-free commutative grammars with integer counters and resets, Decidability and complexity for quiescent consistency and its variations, On reachability equivalence for BPP-nets, State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs, Operational State Complexity and Decidability of Jumping Finite Automata, A type checking algorithm for concurrent object protocols, The Parikh Property for Weighted Context-Free Grammars, Equational theories for automata, On axioms for commutative regular equations without addition., A Fully Equational Proof of Parikh's Theorem