A PTIME-complete matching problem for SLP-compressed words

DOI10.1016/J.IPL.2004.01.002MaRDI QIDQ2390207zbMATH OpenOpenAlexFDO

Authors Nicolas Markey, Philippe Schnoebelen

Publication date 21 July 2009

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

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

zbMATH Keywords

complexitycompressed stringspattern-matching

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1408351
• The complexity of compressed membership problems for finite automata
• Compressed membership in automata with compressed labels
• Algorithmics on SLP-compressed strings: a survey

Cites work

• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Data compression via textual substitution
• Efficient algorithms for Lempel-Ziv encoding
• Finite Monoids: From Word to Circuit Evaluation
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 1490000 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 1408351 (Why is no real title available?)
• scientific article; zbMATH DE number 1418326 (Why is no real title available?)
• On the Tape Complexity of Deterministic Context-Free Languages
• P-complete problems in data compression

Cited in

(5)

• The complexity of compressed membership problems for finite automata
• Compressed membership problems for regular expressions and hierarchical automata
• Leaf languages and string compression
• Complexity of equations over sets of natural numbers
• The complexity of tree automata and XPath on grammar-compressed trees

This page was built for publication: A PTIME-complete matching problem for SLP-compressed words

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