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)
complexitymembership problemcontext-free languagesgrammar-based compressionThue systemsword problems for monoids
Free semigroups, generators and relations, word problems (20M05) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Congruence Closure of Compressed Terms in Polynomial Time, The compressed word problem in relatively hyperbolic groups, Taming the hydra: The word problem and extreme integer compression, The complexity of tree automata and XPath on grammar-compressed trees, Evaluating Matrix Circuits, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, Algorithms for contractibility of compressed curves on 3-manifold boundaries, 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, Compressed Membership in Automata with Compressed Labels, 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, Evaluation of circuits over nilpotent and polycyclic groups, The complexity of compressed membership problems for finite automata, Leaf languages and string compression, Unnamed Item, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, Unnamed Item, Parallel identity testing for skew circuits with big powers and applications, THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES, Unification with Singleton Tree Grammars, The Inclusion Problem of Context-Free Languages: Some Tractable Cases, One-Nonterminal Conjunctive Grammars over a Unary Alphabet, Compressed Word Problems in HNN-Extensions and Amalgamated Products, SLP compression for solutions of equations with constraints in free and hyperbolic groups, Compression techniques in group theory
