## 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 [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 language | English (US) |
---|---|

Pages (from-to) | 368-391 |

Number of pages | 24 |

Journal | Computational Complexity |

Volume | 3 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1993 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Mathematics
- Computational Theory and Mathematics
- Computational Mathematics

## Keywords

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