Commutative grammars: The complexity of uniform word problems

DOI10.1016/S0019-9958(83)80022-9MaRDI QIDQ3327731zbMATH OpenFDO

Authors Dung T. Huynh

Publication date 1983

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

Full work available at URL https://doi.org/10.1016/S0019-9958(83)80022-9

zbMATH Keywords

commutative grammarsfree commutative monoidshierarchyphrase-structure grammarsregular expressions

Mathematics Subject Classification ID

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

Recommendations

• Complexity of problems of commutative grammars
• The complexity of equivalence problems for commutative grammars
• Tightening the complexity of equivalence problems for commutative grammars
• Context-free commutative grammars with integer counters and resets
• scientific article; zbMATH DE number 1059894

Cited in

(20)

• On reachability equivalence for BPP-nets
• Problems on finite automata and the exponential time hypothesis
• Catalytic P systems, semilinear sets, and vector addition systems
• Characterization and complexity results on jumping finite automata
• Context-free commutative grammars with integer counters and resets
• Petri nets and semilinear sets (extended abstract)
• One-Nonterminal Conjunctive Grammars over a Unary Alphabet
• The complexity of equivalence problems for commutative grammars
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Tightening the complexity of equivalence problems for commutative grammars
• Petri nets, commutative context-free grammars, and basic parallel processes
• Normed processes, unique decomposition, and complexity of bisimulation equivalences
• Complexity of problems of commutative grammars
• ON VARIOUS NOTIONS OF PARALLELISM IN P SYSTEMS
• ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE
• Complexity of equations over sets of natural numbers
• One-nonterminal conjunctive grammars over a unary alphabet
• The complexity of knapsack problems in wreath products
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• Complexity of the word problem for commutative semigroups of fixed dimension

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3327731)