Allender, Eric & Bruschi, Danilo & Pighizzini, Giovanni. The complexity of computing maximal word functions. Retrieved from https://doi.org/doi:10.7282/T33F4T6N
AbstractMaximal word functions occur in data retrieval applications and have connections with ranking problems, which in turn were first investigated in relation to data compression [GS]. By the maximal word function" of a language L, 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 is easily computable for certain classes of languages. For a survey, see [He2].
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).
