Commutative grammars: The complexity of uniform word problems

DOI10.1016/S0019-9958(83)80022-9zbMath0541.68044MaRDI QIDQ3327731

Dung T. Huynh

Publication date: 1983

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

zbMATH Keywords

regular expressionshierarchyfree commutative monoidscommutative grammarsphrase-structure grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, etc. in computability and recursion theory (03D40)

Related Items (15)

Catalytic P systems, semilinear sets, and vector addition systems ⋮ Petri nets, commutative context-free grammars, and basic parallel processes ⋮ Petri Nets and Semilinear Sets (Extended Abstract) ⋮ Context-free commutative grammars with integer counters and resets ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On reachability equivalence for BPP-nets ⋮ Complexity of equations over sets of natural numbers ⋮ One-nonterminal conjunctive grammars over a unary alphabet ⋮ ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE ⋮ Normed Processes, Unique Decomposition, and Complexity of Bisimulation Equivalences ⋮ ON VARIOUS NOTIONS OF PARALLELISM IN P SYSTEMS ⋮ One-Nonterminal Conjunctive Grammars over a Unary Alphabet ⋮ Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete ⋮ Characterization and complexity results on jumping finite automata

This page was built for publication: Commutative grammars: The complexity of uniform word problems