Complexity of language recognition problems for compressed words
From MaRDI portal
Recommendations
- Compressed membership problems for regular expressions and hierarchical automata
- Word Problems and Membership Problems on Compressed Words
- Efficient algorithms for Lempel-Ziv encoding
- The complexity of compressed membership problems for finite automata
- Compressed membership in automata with compressed labels
Cited in
(25)- The complexity of compressed membership problems for finite automata
- A PTIME-complete matching problem for SLP-compressed words
- Fixpoint logics over hierarchical structures
- Context-free commutative grammars with integer counters and resets
- Information cost tradeoffs for augmented index and streaming language recognition
- Compressed membership for NFA (DFA) with compressed labels is in NP (P)
- Compressed membership in automata with compressed labels
- Compressed membership problems for regular expressions and hierarchical automata
- Leaf languages and string compression
- Congruence closure of compressed terms in polynomial time
- One-Nonterminal Conjunctive Grammars over a Unary Alphabet
- Compressed Word Problems in HNN-Extensions and Amalgamated Products
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Fast equality test for straight-line compressed strings
- Linear pattern matching of compressed terms and polynomial rewriting
- Efficient algorithms for Lempel-Ziv encoding
- TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
- Grammatical compression: compressed equivalence and other problems
- Automata, Languages and Programming
- Leaf languages and string compression
- Querying and Embedding Compressed Texts
- The fully compressed subgroup membership problem
- Complexity of equations over sets of natural numbers
- Compressed word problems in HNN-extensions and amalgamated products
- One-nonterminal conjunctive grammars over a unary alphabet
This page was built for publication: Complexity of language recognition problems for compressed words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4941166)
