In this work we study some properties of integer compositions in connection with the recognition of rational trace languages. In particular, we introduce some operations defined on integer compositions and present procedures for their computation that work in linear or in quadratic time. These procedures turn out to be useful in the analysis of syntactic trees of certain regular expressions, called repeat-until expressions, which intuitively represent programs of instructions nested in repeat-until loops. Our main aim is to show how, in some cases, such an analysis allows us to design algorithms for the recognition of (rational) trace languages defined by repeat-until expressions, which work in quadratic time independently of the concurrency relation.
|Titolo:||Integer compositions and syntactic trees of repeat-until programs|
GOLDWURM, MASSIMILIANO (Ultimo)
|Data di pubblicazione:||2008|
|Parole Chiave:||Automata and Formal Languages ; Trace Languages|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Citazione:||Integer compositions and syntactic trees of repeat-until programs / L. Breveglieri, S. Crespi Reghizzi, M. Goldwurm. - Presentato al Workshop DNTTT, Developments and New Tracks in Trace Theory, Cremona (9-11 Ottobre 2008), : null, 2008.|
|Appare nelle tipologie:||08 - Relazione interna o rapporto di ricerca|