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. [10.1007/BF01275489]

The complexity of computing maximal word functions

D. Bruschi
Secondo
;
G. Pighizzini
Ultimo
1993

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].
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/178745
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? ND
social impact