Fast equality test for straight-line compressed strings

DOI10.1016/j.ipl.2012.01.008zbMath1243.68324OpenAlexW2009408613MaRDI QIDQ436321

Georg Schnitger, Manfred Schmidt-Schauss

Publication date: 20 July 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.01.008

zbMATH Keywords

straight-line programsrandomized algorithmsgrammar-based compression

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items (4)

Equality Testing of Compressed Strings ⋮ Linear pattern matching of compressed terms and polynomial rewriting ⋮ Fast equality test for straight-line compressed strings ⋮ Parameter reduction and automata evaluation for grammar-compressed trees

Cites Work

• Unnamed Item
• Unnamed Item
• Fast equality test for straight-line compressed strings
• On the complexity of pattern matching for highly compressed two-dimensional texts.
• Approximate formulas for some functions of prime numbers
• Processing Compressed Texts: A Tractability Border
• A universal algorithm for sequential data compression
• Database Programming Languages

This page was built for publication: Fast equality test for straight-line compressed strings