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.
EnglishWe present an algorithm for the recognition of rational trace languages that has a time complexity at most proportional to the number of prefixes of the input trace. In the worst case it requires O(nα) time and O(nα-1) space, where α is the size of the maximum clique in the independence alphabet; in the average case, it works in O (nk) time, where k is the number of connected components of the dependence alphabet. This algorithm is based on a dynamic programming technique that can also be applied for the recognition of context-free trace languages. Here we present an extension of the classical CYK algorithm that requires O (n3α) time and O (n2α) space in the worst case, and O (n3k) time and O (n2k) space in the average case.
Analysis of algorithms for the recognition of rational and context-free trace languages / A. Avellone, M. Goldwurm. - In: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS. - ISSN 0988-3754. - 32:4-5-6(1998), pp. 141-152.
| Titolo: | Analysis of algorithms for the recognition of rational and context-free trace languages |
| Autori: | GOLDWURM, MASSIMILIANO (Ultimo) |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 1998 |
| Rivista: | |
| Tipologia: | Article (author) |
| Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
Copyright © 2021