Word Problems and Membership Problems on Compressed Words
From MaRDI portal
complexitycontext-free languagesgrammar-based compressionmembership problemThue systemsword problems for monoids
Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)
Recommendations
- Automata, Languages and Programming
- The Compressed Word Problem for Groups
- scientific article; zbMATH DE number 1738654
- Algorithmic Combinatorics on Partial Words
- Combinatorics of Compositions and Words
- Compressed Word Problems in HNN-Extensions and Amalgamated Products
- The compressed word problem in relatively hyperbolic groups
- Compression of Words Over a Partially Commutative Alphabet
- Compressed word problems in HNN-extensions and amalgamated products
- The complexity of compressed membership problems for finite automata
Cited in
(39)- Pseudo-natural algorithms for finitely generated presentations of monoids and groups
- Evaluation of circuits over nilpotent and polycyclic groups
- Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups.
- Compression techniques in group theory
- The compressed word problem in relatively hyperbolic groups
- The complexity of compressed membership problems for finite automata
- Parallel identity testing for skew circuits with big powers and applications
- Compressed membership in automata with compressed labels
- Compressed membership problems for regular expressions and hierarchical automata
- The inclusion problem of context-free languages: some tractable cases
- Compressed word problems for inverse monoids
- Congruence closure of compressed terms in polynomial time
- Evaluating matrix circuits
- One-Nonterminal Conjunctive Grammars over a Unary Alphabet
- Compressed Word Problems in HNN-Extensions and Amalgamated Products
- Unification with Singleton Tree Grammars
- The Inclusion Problem of Context-Free Languages: Some Tractable Cases
- Taming the hydra: the word problem and extreme integer compression
- Parallel identity testing for skew circuits with big powers and applications
- scientific article; zbMATH DE number 1834672 (Why is no real title available?)
- Compressed decision problems for graph products and applications to (outer) automorphism groups.
- Efficient algorithms for highly compressed data: the word problem in Higman's group is in P.
- scientific article; zbMATH DE number 1408351 (Why is no real title available?)
- Compressed decision problems in hyperbolic groups
- The power word problem
- SLP compression for solutions of equations with constraints in free and hyperbolic groups.
- The Compressed Word Problem for Groups
- Grammatical compression: compressed equivalence and other problems
- Automata, Languages and Programming
- Leaf languages and string compression
- On the word problem for weakly compressible monoids
- Algorithms for contractibility of compressed curves on 3-manifold boundaries
- 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
- Compressed decision problems in hyperbolic groups
- Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
- Algorithms for contractibility of compressed curves on 3-manifold boundaries
- The complexity of tree automata and XPath on grammar-compressed trees
This page was built for publication: Word Problems and Membership Problems on Compressed Words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470731)
