The complexity of computing maximal word functions
From MaRDI portal
data compressiondata retrievalmaximal word functionsone-way nondeterministic auxiliary pushdown automataparallel algorithmranking
Information storage and retrieval of data (68P20) Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Distributed algorithms (68W15)
Recommendations
- scientific article; zbMATH DE number 176526
- scientific article; zbMATH DE number 1992419
- Properties of the complexity function for finite words
- Computing maximal-exponent factors in an overlap-free word
- scientific article; zbMATH DE number 3892611
- Maximal pattern complexity of words over \(\ell\) letters
- scientific article; zbMATH DE number 1091206
- Proof of a conjecture on word complexity
- Symbolic analysis of finite words: the complexity function
- Optimal computation of overabundant words
Cites work
- A taxonomy of problems with fast parallel algorithms
- A very hard log-space counting class
- An Optimal Parallel Algorithm for Formula Evaluation
- Bounding Fan-out in Logical Networks
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Compression and Ranking
- Constant Depth Reducibility
- Depth reduction for noncommutative arithmetic circuits
- EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
- Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 403952 (Why is no real title available?)
- scientific article; zbMATH DE number 1142306 (Why is no real title available?)
- On the complexity of ranking
- On the Efficient Generation of Language Instances
- On uniform circuit complexity
- On uniformity within \(NC^ 1\)
- Optimization of LR(k) parsers
- P-Printable Sets
- P-uniform circuit complexity
- Parity, circuits, and the polynomial-time hierarchy
- Properties that characterize LOGCFL
- Random generation of combinatorial structures from a uniform distribution
- Ranking and formal power series
- Rudimentary reductions revisited
- The complexity of computing the number of strings of given length in context-free languages
- The Complexity of Enumeration and Reliability Problems
- The complexity of optimization problems
- The complexity of ranking simple languages
- Two Applications of Inductive Counting for Complementation Problems
- Two dynamic programming algorithms for which interpreted pebbling helps
Cited in
(10)- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- A quasi-polynomial-time algorithm for sampling words from a context-free language
- How hard is computing the edit distance?
- A note on logspace optimization
- Random Generation for Finitely Ambiguous Context-free Languages
- String distances and intrusion detection: Bridging the gap between formal languages and computer security
- How hard is to compute the edit distance
- On languages accepted with simultaneous complexity bounds and their ranking problem
- The intractability of computing the Hamming distance
- Proof of a conjecture on word complexity
This page was built for publication: The complexity of computing maximal word functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1321032)
