The complexity of computing maximal word functions

Eric Allender, Danilo Bruschi, Giovanni Pighizzini

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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 [21]. By the "maximal word function" of a language L {subset double equals} ∑*, 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. For a survey, see [24].

Original languageEnglish (US)
Pages (from-to)368-391
Number of pages24
JournalComputational Complexity
Issue number4
StatePublished - Dec 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics


  • Subject classifications: 68Q15, 68Q25, 68Q45


Dive into the research topics of 'The complexity of computing maximal word functions'. Together they form a unique fingerprint.

Cite this