The complexity of compressed membership problems for finite automata
From MaRDI portal
Publication:2254509
DOI10.1007/s00224-013-9443-6zbMath1319.68134OpenAlexW1755286175WikidataQ59394998 ScholiaQ59394998MaRDI QIDQ2254509
Publication date: 5 February 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-013-9443-6
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Approximation of smallest linear tree grammar ⋮ The fully compressed subgroup membership problem ⋮ Approximation of grammar-based compression via recompression ⋮ One-variable word equations in linear time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of equations over sets of natural numbers
- One-nonterminal conjunctive grammars over a unary alphabet
- Maintaining dynamic sequences under equality tests in polylogarithmic time
- Practical and flexible pattern matching over Ziv-Lempel compressed text.
- Pattern matching and membership for hierarchical message sequence charts
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- A PTIME-complete matching problem for SLP-compressed words
- Multi-method dispatching
- Faster Fully Compressed Pattern Matching by Recompression
- Algorithmics on SLP-compressed strings: A survey
- Simple and Efficient LZW-Compressed Multiple Pattern Matching
- Pattern matching in compressed texts
- Compressed Membership in Automata with Compressed Labels
- COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA
- Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
- Efficient Computation in Groups Via Compression
- The Smallest Grammar Problem
- COMPRESSED WORDS AND AUTOMORPHISMS IN FULLY RESIDUALLY FREE GROUPS
- Satisfiability of word equations with constants is in PSPACE
- Finite Monoids: From Word to Circuit Evaluation
- Efficient algorithms for Lempel-Ziv encoding
- Word Problems and Membership Problems on Compressed Words
- Querying and Embedding Compressed Texts
- Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes
This page was built for publication: The complexity of compressed membership problems for finite automata
