The complexity of computing maximal word functions
Eric Allender
Department of Computer Science
Rutgers University
New Brunswick
New Jerwey 08903, USA
Danilo Bruschi and Giovanni Pighizzini
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
Abstract
Maximal word functions occur in data retrieval applications and have
connections with ranking problems, which in turn were first investigated
in relation to data compression. By the ``maximal
word function'' of a language $L\subseteq\Sigma^*$, we mean the problem of
finding, on input $x$, the lexicographically largest word belonging to $L$
that is smaller than or equal to $x$.
In this paper we present a parallel algorithm for computing maximal word
functions for languages recognized by one--way nondeterministic auxiliary
pushdown automata (and hence for the class of context--free languages).
This paper is a continuation of a stream of research focusing on the
problem of identifying properties others than membership which are easily
computable for certain classes of languages.