The complexity of equivalence problems for commutative grammars

DOI10.1016/S0019-9958(85)80015-2zbMath0601.68048MaRDI QIDQ3736915

Dung T. Huynh

Publication date: 1985

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

computational complexitydecidabilityregular grammarscontext-free commutative grammarscontext-sensitive commutative grammarsinequivalence problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (10)

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

This page was built for publication: The complexity of equivalence problems for commutative grammars