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. BruschiSecondo
;G. PighizziniUltimo
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].Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.