IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishMaximal 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].
| 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): | 10.1007/BF01275489 |
| Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
http://hdl.handle.net/2434/178745
Copyright © 2019