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 [GS]. By the maximal word function" of a language L, 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 is easily computable for certain classes of languages. For a survey, see [He2].