Word problems on compressed words

DOI10.1007/978-3-540-27836-8_76MaRDI QIDQ5466524zbMATH OpenOpenAlexFDO

Authors Markus Lohrey

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Word Problems and Membership Problems on Compressed Words
• The complexity of compressed membership problems for finite automata
• Compressed word problems for inverse monoids
• Complexity of language recognition problems for compressed words
• Grammatical compression: compressed equivalence and other problems

Cited in

(11)

• Compressed word problems for inverse monoids
• Leaf languages and string compression
• Dynamic word problems
• Polynomial braid combing
• Word problems for 2-homogeneous monoids and symmetric logspace
• Equivalence of Linear Tree Transducers with Output in the Free Group
• Logspace and compressed-word computations in nilpotent groups
• On constructing possibly one-way functions based on the non-decidability of the endomorphism problem in groups
• Grammatical compression: compressed equivalence and other problems
• Word Problems and Membership Problems on Compressed Words
• On the word problem for weakly compressible monoids

This page was built for publication: Word problems on compressed words

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