The complexity of computing maximal word functions

DOI10.1007/BF01275489zbMath0802.68061DBLPjournals/cc/AllenderBP93WikidataQ61677541 ScholiaQ61677541MaRDI QIDQ1321032

Danilo Bruschi, Giovanni Pighizzini, Eric W. Allender

Publication date: 8 May 1994

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

rankingdata compressionparallel algorithmdata retrievalmaximal word functionsone-way nondeterministic auxiliary pushdown automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Data encryption (aspects in computer science) (68P25) Information storage and retrieval of data (68P20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Related Items (9)

How hard is to compute the edit distance ⋮ A note on logspace optimization ⋮ A quasi-polynomial-time algorithm for sampling words from a context-free language ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ The intractability of computing the Hamming distance ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ String distances and intrusion detection: Bridging the gap between formal languages and computer security ⋮ How hard is computing the edit distance? ⋮ Random Generation for Finitely Ambiguous Context-free Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of ranking
• Random generation of combinatorial structures from a uniform distribution
• The complexity of optimization problems
• On uniform circuit complexity
• Properties that characterize LOGCFL
• The complexity of computing the number of strings of given length in context-free languages
• Rudimentary reductions revisited
• A very hard log-space counting class
• Two dynamic programming algorithms for which interpreted pebbling helps
• Optimization of LR(k) parsers
• On uniformity within \(NC^ 1\)
• Ranking and formal power series
• Bounding Fan-out in Logical Networks
• On the Efficient Generation of Language Instances
• The complexity of ranking simple languages
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• P-uniform circuit complexity
• A taxonomy of problems with fast parallel algorithms
• Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
• Two Applications of Inductive Counting for Complementation Problems
• The Complexity of Enumeration and Reliability Problems
• Compression and Ranking
• EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
• An Optimal Parallel Algorithm for Formula Evaluation
• P-Printable Sets
• Depth reduction for noncommutative arithmetic circuits
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: The complexity of computing maximal word functions