Fast equality test for straight-line compressed strings
The paper describes a simple and fast randomized test for equality of grammar-compressed strings. The thorough running time analysis is done by applying a logarithmic cost measure. Keywords: randomized algorithms, straight line programs, grammar-based compression
| Author: | Manfred Schmidt-Schauß, Georg Schnitger |
|---|---|
| URN: | urn:nbn:de:hebis:30-115464 |
| URL: | http://www.ki.informatik.uni-frankfurt.de/papers/schauss/randomPlandowskiIB45.pdf |
| Series (Serial Number) | Technical report Frank / Johann-Wolfgang-Goethe-Universität, Fachbereich Informatik und Mathematik, Institut für Informatik (45) |
| Publisher: | Johann Wolfgang Goethe-Univ., Fachbereich Informatik und Mathematik, Inst. für Informatik, Research group for Artificial Intelligence and Software Technology |
| Place of publication: | Frankfurt [am Main] |
| Document Type: | Working Paper |
| Language: | English |
| Date of Publication (online): | 15.09.2011 |
| Year of first Publication: | 2011 |
| Publishing Institution: | Univ.-Bibliothek Frankfurt am Main |
| Tag: | grammar-based compression; randomized algorithms ; straight line programs |
| HeBIS PPN: | 277091950 |
| Institutes: | Informatik |
| Dewey Decimal Classification: | 004 Datenverarbeitung; Informatik |
| Licence (German): |  Veröffentlichungsvertrag für Publikationen ohne Print on Demand |
