Vai al contenuto| Home page|

   Ti trovi in: HOME »Programmi, progetti e risultati »I progetti »PRIN - Programmi di ricerca di Rilevante Interesse Nazionale»Programma di ricerca
INIZIO_TESTO_DA_INDICIZZARE

PROGRAMMA DI RICERCA 2005

italiano - english
Unità di Ricerca
Programmi di ricerca simili:
Classificazione scientifico-disciplinare
Classificazione brevettuale
Classificazione geografica
Bibliografia
[RoSa] G. Rozenberg, A. Salomaa (Eds), Handbook of Formal Languages, Springer, 1997
[BCGL] A. Bertoni, C. Choffrut, M. Goldwurm, V. Lonati, On the number of occurrences of a symbol in words of regular languages. TCS 302:431-456, 2003
[BMT] A. Bertoni, G. Mauri, M. Torelli, Some Recursive Unsolvable Problems Relating to Isolated Cutpoints in Probabilistic Automata. ICALP 1977: 87-94
[BC] A. Bertoni, M. Carpentieri, Regular languages accepted by quantum automata, Inf.Comp.165, 174-182, 2001
[BMP] A. Bertoni, C. Mereghetti, B. Palano, Quantum Computing: 1-Way Quantum Automata. DLT 2003: 1-20
[KW] A. Kondacs, J. Watrous, On the Power of Quantum Finite State Automata, In. Proc. 36th IEEE FOCS, 66-75, 1997
[DJK] H. Derksen, E. Jeandel, P. Koiran, Quantum automata and algebraic groups, J. Symb. Comp. 39(3-4):357-371, 2005
[CMP]A.Cherubini, J.Meakin, B.Piochi, Amalgams of finite inverse semigroups, J.Alg. 285, (2005), 706-725
[AC] D.Ananichev, A.Cherubini, M.Volkov, Image reducing words and subgroups of free groups, TCS, 307 (203) 77-92
[MP] C. Mereghetti, G. Pighizzini, Optimal Simulations Between Unary Automata. SIAM J. Comp. 30:1976-1992, 2001
[MR] P. Massazza, R. Radicioni, On computing the coefficients of rational formal series. FPSAC'04, 211-226, 2004
[BaDLPP] E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani, ECO: a Methodology for the Enumeration of Combinatorial Objects, Journal of Diff. Equ. and Appl., 5 (1999) 435-490.
[BB] J. Berstel, L. Boasson. Formal properties of XML grammars and languages. Acta Inf. 38:649-671, 2002.
[BedL] J. Berstel and A. de Luca. Sturmian words, lyndon words and trees. TCS, (178):171-203, 1997.
[BerP] J. Berstel, D. Perrin, Theory of Codes, Academic Press, 1985.
[BRe] F. Burderi and A. Restivo. Varieties of codes and kraft inequality. STACS 2005.
[BW] M. Burrows and D.J. Wheeler. A block sorting data compression algorithm. Tech. report, DSRC, 1994.
[CdL7] A. Carpi, A. de Luca, Codes of central Sturmian words, TCS, to appear.
[CK] C. Choffrut and J. Karhumäki. Combinatorics on words. In Handbook of Formal Languages, G. Rosenberg and A. Salomaan(eds.), vol. 1, ch. 6, 329-438. Springer, 1997.
[CPS] S. Crespi Reghizzi, M.Pradella,P. San Pietro, Conciseness of Associative Language Descriptions, Computer Languages, 2002.
[ChDPe] M. Crochemore, J. Désarménien, and D. Perrin. A note on the Burrows-Wheeler transformation. TCS, 332:567-572, 2005.
[DF] C. De Felice, A partial result about the factorization conjecture for finite variable-length codes, Discrete Math., 122 (1993) 137-152.
[dLV] A. de Luca and S. Varricchio, Finiteness and regularity in semigroups and formal languages, EATCS Monographs on Theoretical Computer Science,Springer 1999
[EHR] A. Ehrenfeucht, D. Haussler and G. Rozenberg, On regularity of context-free languages, TCS 27 (1983) 311-332
[GeR] I. M. Gessel and C. Reutenauer. Counting permutations with given cycle structure and descent set. J. Combin. Theory Ser. A, 64(2):189--215, 1993
[Guz] F. Guzmán, Decipherability of codes, Journal of Pure and Applied Algebra, 141 (1999) 13-35
[HPP] T. Head, Gh. Paun, D. Pixton. Language theory and molecular genetics, Handbook of Formal Languages Vol.2, Springer, 1997
[Hi] G. H. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. 3 (1952) 326-336
[Lot1] M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics. Addison¬Wesley, 1983
[Lot2] M. Lothaire. Algebraic Combinatorics on Words. Cambridge University Press, 2002
[MaReS1] S. Mantaci, A. Restivo, and M. Sciortino. Burrows-Wheeler transform and Sturmian words. IPL, 86:241-246, 2003
[MaReS2] S. Mantaci, A. Restivo, and M. Sciortino. An extension of the Burrows-Wheeler Transform to k words. Proc. of DCC 2005, (pp.469) J.E. Storer,M.Cohn (eds) IEEE Computer Society Press
[MReS2] F. Mignosi, A. Restivo, and M. Sciortino. Words and Forbidden Factors. TCS, 273(1-2):99-117, 2001
[MoH] M. Morse and G. A. Hedlund. Symbolic dynamics II: Sturmian trajectories. Amer. J. Math., (62):1-42, 1940
[Pa] Gh. Paun, Computing with membranes, J. Comput. System Sci. 61, 1, 108-143, (2000)
[PS] D. Perrin, M.P. Schutzenberger, Un probleme elementaire de la theorie de l'information, Theorie de l'Information, Colloques Internat. CNRS 276, Cachan (1977) 294-260
[Re] C. Reutenauer, Non commutative factorization of variable-length codes, J. Pure and Applied Algebra 36 (1985) 167-186
[Sav] C. Savage, A survey of combinatorial Gray codes, SIAM Rev. 39 (4), 605-629 (1997)
[Sch] M.P. Schützenberger, Context-free languages and pushdown automata, Information and Control 6 (1963) 246-264
[S] J. Seward. The bzip2 home page, 1997. http://sources.redhat.com/bzip2
[ZG] L. Zhang, C.K. Gu, Two classes of factorizing codes - (p,p)-codes and (4,4)-codes, in "Words, Languages and Combinatorics II" (M. Ito, H. Jurgensen, eds.), World Scientific (1994) 477-483
[AGM] M. Anselmo, D. Giammarresi, M. Madonia, Regular expressions for two-dimensional languages over one-letter alphabet, LNCS (2004), 3340, 63-75, Springer-Verlag
[BH] M. Blum and C.E. Hewitt. Automata on two¬dimensional tape. Proc. IEEE Symp. on Found. of Comp. Sci., 8, 1967
[CR1] G. Castiglione, A. Restivo. Reconstruction of L-convex polyominoes. Electronic Notes Discr. Math., 12, 2003
[CR2] G. Castiglione, A. Restivo. Ordering and convex polyominoes. LNCS(2005), 3354
[CFRR1] G. Castiglione, A. Frosini, A. Restivo S. Rinaldi. Enumeration of L-convex polyominoes. TCS,to appear
[DV] M.P. Delest, G. Viennot: Algebraic languages and polyominoes enumeration, TCS vol. 34 (1984) 169-206
[CFRR2] G. Castiglione, A. Frosini, A. Restivo S. Rinaldi. A tomographical characterization of L-convex polyominoes. LNCS(2005)
[CP] S. Crespi-Reghizzi, M. Pradella: Tile Rewriting Grammars, LNCS(2003) 2710, 206-217
[GR] D. Giammarresi, A. Restivo. Two-dimensional languages. In A. Salomaa and G. Rozenberg(eds) Handbook of Formal Languages, vol 3, 215—267,Springer-Verlag, 1997
[Go] S.W. Golomb. Polyominoes. Charles Scribner's Sons, New York, 1965
[HK] G.T. Herman, A. Kuba (Eds.). Discrete Tomography: Foundations, Algorithms and Applications. Birkhauser, 1999
[IT] K. Inoue, I. Takanami. A survey of two-dimensional automata theory. Inf. Sci., 55(1-3):99-121, 1991
[Mi] M. L. Minsky. Step toward artificial intelligence. In Proc. IRE, vol. 49, 1961
[Ro] A. Rosenfeld. Picture Languages. Academic Press, 1979
[AD] R. Alur and D. Dill, Automata for modeling real-time systems, TCS 126, (1994) 183-236
[GDIS] G. Xie, Z. Dang, O. Ibarra, P. San Pietro, Dense counter machines and verification problems, CAV03
[IDS] Z. Dang, O. Ibarra, P. San Pietro, G. Xie. Real-Counter Automata and Applications to Verification, FSTTCS 2004
[V] M. Vardi, Alternating Automata: Unifying Truth and Validity Checking for Temporal Logics. LNCS 1249 (1997) 191-206
[BGS] D. Bacon, S. Graham, O. Sharp, Compiler Transformations for High-Performance Computing, in ACM Comp. Surv., vol. 26(4),345-419, 1994
[DR] V. Diekert, G. Rozenberg eds, The Book of Traces, World Scientific 1995
[WL] M. E. Wolf and M. S. Lam. A loop transformation theory and an algorithm to maximize parallelism. Transactions on Parallel and Distributed Systems, 2(4):452–470, October 1991
[BKM] A. Broder, R. Kumar, F. Maghoul et al., Graph structure in the web: experiments and models. In Proc. WWW Conf., 2000
[BV] P. Boldi and S. Vigna. The WebGraph framework I: Compression techniques. In Proc. of WWW Conf.,595-601, 2004
[CM] J. Cho, H. Garcia-Molina. Parallel crawlers. In Proc. of WWW Conf., 2002
[NW] M. Najork, J. L. Wiener. Breadth-first search crawling yields high-quality pages. In Proc. of WWW Conf., 2001
[WMB] I.H. Witten, A. Moffat, T.C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufman, Los Altos, 1999
[GoWi] M. Goldwurm, K. Wich, Unambiguous Turn Position and Rational Traces Languages, Preliminary Rep., 2005
[Ma] P.Massazza, The inclusion problem for unambiguous rational trace languages, Prel. Rep., 2005
Parole Chiave
LINGUAGGI FORMALI; TEORIA DEGLI AUTOMI; GRAMMATICHE; COMBINATORIA DELLE PAROLE; METODI SINTATTICI; LINGUAGGI BIDIMENSIONALI; LINGUAGGI TRACCIA

Automi e Linguaggi Formali: aspetti matematici e applicativi

Università degli Studi di Palermo
Abstract
Il progetto si propone di far avanzare la conoscenza della teoria degli automi e la sua applicabilità a problemi scientifici e tecnologici.
La ricerca utilizzerà sia approcci classici, come la combinatoria e i semigruppi, sia nuovi strumenti concettuali dell'algebra non commutativa, della logica, della teoria della probabilità e della dinamica simbolica. Potenziali applicazioni scientifiche includono fra le altre, la codifica, la biologia, le scienze cognitive e neurologiche, la compilazione e la verifica del software, le risorse del web.
La cooperazione interdisciplinare fra matematici, informatici teorici e ingegneri permetterà una sinergia tra la ricerca fondamentale e lo studio di nuovi modelli formali orientati alle applicazioni.
In uno scenario dove un gruppo di scienziati qualificato e di studenti di dottorato può comunicare e condividere sia le sfide provenienti da nuove applicazioni della teoria degli automi, sia le intuizione teoriche, questo programma catalizzerà progressi in entrambe le direzioni.
Evitando dispersioni sull'intero settore, sarà affrontato un campo limitato di direzioni di ricerca.


A1) Modelli di Automi, serie formali, e loro proprietà
Studio di modelli computazionali quali gli automi quantistici, mediante l'analisi dei loro comportamenti descritti da linguaggi formali. Studio della complessità descrizionale di automi con vincoli di risorse. Proprietà algebriche di automi a stati finiti >>>

Coordinatore Scientifico del Programma di Ricerca
Antonio RESTIVO Università degli Studi di PALERMO
Obiettivo del Programma di Ricerca
La Teoria degli automi (AT) è una delle aree dell'informatica affermate da più lungo tempo. Negli ultimi anni, la AT non solo si è sviluppata in molte direzioni diverse, ma si è anche evoluta a vari livelli: l'esplorazione di nuovi modelli ed applicazioni ha, nello stesso tempo, stimolato una grande varietà di profonde teorie matematiche. Più azioni coordinate svilupperanno la conoscenza della AT e la applicabilità a difficili problemi scientifici e tecnologici.
Applicazioni standard in informatica della AT includono fra le altre, la compilazione e la verifica del software. Negli ultimi anni nuove applicazioni di concetti della AT sono emerse dalla biologia, dalla fisica, dalle scienze neuro-cognitive, dalla tomografia, dalla linguistica, etc., mentre gli sviluppi della tecnologia informatica hanno incrementato il bisogno di una progettazione formale e di metodi di verifica per far fronte problemi come la sicurezza e i servizi delle reti e le risorse del web. La lista non è esaustiva, poiché la AT ambisce a rivolgersi verso nuove applicazioni, come l'analisi di immagini, uno dei punti principali di questo progetto.
Nello stesso tempo, le basi matematiche della AT si trovano in settori della matematica sempre più avanzati. Mentre nei primi anni sessanta era sufficiente la sola teoria dei grafi elementare e la combinatoria, ultimamente sono stati introdotti con successo nuovi strumenti provenienti dall'algebra non commutativa, dalla logica, dalla teorie della >>>

Durata
24 mesi
Base di partenza scientifica nazionale o internazionale
La Teoria degli Automi e dei Linguaggi Formali è un ampio e ancora in crescita corpo di conoscenze. I risultati classici ed i più recenti sviluppi di tale teoria sono raccolti in [RoSa]. La base di partenza scientifica relativa ai temi delle ricerche proposte viene data nel seguito riferendosi ai punti del programma riportati nella Sezione 2.1.

A1)Modelli di Automi, serie formali, e loro proprietà.
A partire dal lavoro di Rabin e Scott, gli automi sono stati oggetto di studi di ampio spettro, con contributi in aree dalle architetture di calcolo all'algebra. Richiamiamo qui alcune recenti estensioni del modello di automa al caso quantistico, alcune recenti interazioni tra la teoria degli automi e lo studio di strutture algebriche, contributi in ambito di complessità descrizionale, l'uso di tecniche di manipolazione con serie formali quali quelle olonomiche per problemi di conteggio e generazione casuale.
Fra le recenti estensioni, vanno segnalati i vari modelli di automi quantistici a stati finiti [BC,KW]. Proprietà di questi modelli sono utili per indagare i vantaggi computazionali dell'interferenza quantistica. Ci sono analogie col caso probabilistico; per esempio, Rabin ha provato che i comportamenti di automi con taglio isolato sono esattamente i linguaggi regolari; via proprietà di serie formali, questo risultato può essere esteso a numerosi modelli di automi quantistici [BMP]. Per altre proprietà, gli automi quantistici esibiscono >>>