Maximal word functions occur in data retrival applications and have connections with ranking problems i.e. with problems related to data compression. Compute the maximal word function of a string x with respect to a language L is contained in or equal to SIGMA* consists in determining the lexicographically greatest word belonging to L, which is smaller than or equal to x. In this paper we investigate the complexity of computing maximal word functions, establishing sharp boundaries between classes of languages for which the maximal word function can be efficiently computed and classes of languages for which such a problem seems to be difficult to solve. For example, we will show that the maximal word function for the class of context free languages is in a AC2 while for the class of languages accepted by 2-way pushdown automata the maximal word function can be efficiently (polynomially) computed if and only if P = NP. We will also show connections with ranking, detector and constructor functions as introduced in [14]. This paper is a continuation of the study enterprised by many authors ([6], [10], [13] and [14]) with the intention of identifying properties other than membership which are easily computable for certain class of languages.
THE COMPLEXITY OF COMPUTING MAXIMAL WORD FUNCTIONS / D. Bruschi, G. Pighizzini - In: Fundamentals of Computation Theory : 8. international conference, FCT '91 : Gosen, Germany, September 9-13, 1991 / [a cura di] L. Budach. - Berlin : Springer-Verlag, 1991. - ISBN 3540544585. - pp. 157-167 (( Intervento presentato al 8. convegno International Conference FCT tenutosi a Gosen, Germany nel 1991.
THE COMPLEXITY OF COMPUTING MAXIMAL WORD FUNCTIONS
D. BruschiPrimo
;G. PighizziniUltimo
1991
Abstract
Maximal word functions occur in data retrival applications and have connections with ranking problems i.e. with problems related to data compression. Compute the maximal word function of a string x with respect to a language L is contained in or equal to SIGMA* consists in determining the lexicographically greatest word belonging to L, which is smaller than or equal to x. In this paper we investigate the complexity of computing maximal word functions, establishing sharp boundaries between classes of languages for which the maximal word function can be efficiently computed and classes of languages for which such a problem seems to be difficult to solve. For example, we will show that the maximal word function for the class of context free languages is in a AC2 while for the class of languages accepted by 2-way pushdown automata the maximal word function can be efficiently (polynomially) computed if and only if P = NP. We will also show connections with ranking, detector and constructor functions as introduced in [14]. This paper is a continuation of the study enterprised by many authors ([6], [10], [13] and [14]) with the intention of identifying properties other than membership which are easily computable for certain class of languages.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.