Word Problems and Membership Problems on Compressed Words

From MaRDI portal
Publication:5470731

DOI10.1137/S0097539704445950zbMath1106.20043MaRDI QIDQ5470731

Markus Lohrey

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)




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