Word Problems and Membership Problems on Compressed Words
From MaRDI portal
Publication:5470731
DOI10.1137/S0097539704445950zbMath1106.20043MaRDI QIDQ5470731
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
complexity; membership problem; context-free languages; grammar-based compression; Thue systems; word problems for monoids
20M05: Free semigroups, generators and relations, word problems
68Q42: Grammars and rewriting systems
20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Taming the hydra: The word problem and extreme integer compression, Parallel identity testing for skew circuits with big powers and applications, COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS, EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P, SLP compression for solutions of equations with constraints in free and hyperbolic groups, Leaf languages and string compression, Complexity of equations over sets of natural numbers, Compressed word problems in HNN-extensions and amalgamated products, One-nonterminal conjunctive grammars over a unary alphabet, The complexity of tree automata and XPath on grammar-compressed trees, Evaluation of circuits over nilpotent and polycyclic groups, The complexity of compressed membership problems for finite automata, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, Compressed Membership in Automata with Compressed Labels, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES, Congruence Closure of Compressed Terms in Polynomial Time, Evaluating Matrix Circuits, One-Nonterminal Conjunctive Grammars over a Unary Alphabet, Compressed Word Problems in HNN-Extensions and Amalgamated Products, Unification with Singleton Tree Grammars, The Inclusion Problem of Context-Free Languages: Some Tractable Cases
