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].
The complexity of computing maximal word functions / E. Allender, D. Bruschi, G. Pighizzini. - In: COMPUTATIONAL COMPLEXITY. - ISSN 1016-3328. - 3:4(1993 Oct), pp. 368-391.
Titolo: | The complexity of computing maximal word functions |
Autori: | BRUSCHI, DANILO MAURO (Secondo) PIGHIZZINI, GIOVANNI (Ultimo) |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | ott-1993 |
Rivista: | |
Tipologia: | Article (author) |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/BF01275489 |
Appare nelle tipologie: | 01 - Articolo su periodico |