Commutative grammars: The complexity of uniform word problems
From MaRDI portal
Publication:3327731
DOI10.1016/S0019-9958(83)80022-9zbMath0541.68044MaRDI QIDQ3327731
Publication date: 1983
Published in: Information and Control (Search for Journal in Brave)
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
