The complexity of computing maximal word functions
type: Item
instance of: scholarly article
title: The complexity of computing maximal word functions
zbMATH Open document ID: 0802.68061
DOI: 10.1007/BF01275489
author: Danilo Bruschi
author: Giovanni Pighizzini
author: Eric Allender
published in: Computational Complexity
publication date: 1994-05-08T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P25
zbMATH DE Number: 561485
zbMATH Keywords: data retrieval
zbMATH Keywords: ranking
zbMATH Keywords: data compression
zbMATH Keywords: parallel algorithm
zbMATH Keywords: maximal word functions
zbMATH Keywords: one-way nondeterministic auxiliary pushdown automata
Wikidata QID: Q61677541
MaRDI profile type: Publication
cites work: Optimization of LR(k) parsers
cites work: P-uniform circuit complexity
cites work: Rudimentary reductions revisited
cites work: Depth reduction for noncommutative arithmetic circuits
cites work: P-Printable Sets
cites work: A very hard log-space counting class
cites work: On uniformity within \(NC^ 1\)
cites work: Ranking and formal power series
cites work: The complexity of computing the number of strings of given length in context-free languages
cites work: Two Applications of Inductive Counting for Complementation Problems
cites work: An Optimal Parallel Algorithm for Formula Evaluation
cites work: Constant Depth Reducibility
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Compression and Ranking
cites work: On the complexity of ranking
cites work: Q4201936
cites work: Bounding Fan-out in Logical Networks
cites work: Q3862379
cites work: The complexity of ranking simple languages
cites work: EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: Q4385522
cites work: The complexity of optimization problems
cites work: Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
cites work: On uniform circuit complexity
cites work: On the Efficient Generation of Language Instances
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Properties that characterize LOGCFL
cites work: Two dynamic programming algorithms for which interpreted pebbling helps
DBLP publication ID: journals/cc/AllenderBP93
Recommended article: Q4035692
Recommended article: Q4432080
Recommended article: Q5201214
Recommended article: Computing maximal-exponent factors in an overlap-free word
Recommended article: Q5184423
Recommended article: Maximal pattern complexity of words over \(\ell\) letters
Recommended article: Q4366995
Recommended article: Proof of a conjecture on word complexity
Recommended article: Symbolic analysis of finite words: the complexity function
Recommended article: Optimal Computation of Overabundant Words
description: scientific article; zbMATH DE number 561485