Seminar 30 November 2006 - Laura Bozzelli

Speaker: Laura Bozzelli
Date: 30 November 2006
Time: 11am
Place: via Carloni 78, Sala Riunione
Title: Model checking problem for Process Rewrite Systems
Abstract:
We consider the model checking problem for Process Rewrite Systems (PRS), an infinite-state formalism (non Turing-powerful) which subsumes many common models such as Pushdown Processes, Petri Nets, and PA processes. PRS can be adopted as a formal model for programs with dynamic creation and (a restricted form of) synchronization of concurrent processes, and with recursive procedures.
We establish an exact decidability boundary of the model checking problem for PRS against properties described by basic fragments of action-based Linear Temporal Logic (LTL). It is known that the problem for general LTL properties is decidable for Petri nets and for pushdown processes, while it is undecidable for PA processes. As our main result, we show that the problem is decidable for PRS if we consider properties defined by formulae with only modalities "strict eventually" and "strict always". Moreover, we show that the problem remains undecidable for PA processes even with respect to the LTL fragment with the only modality "until" or the fragment with modalities "next" and "infinitely often".

ESF Workshop 18-20 October 2006

 Automata and formal languages for DNA computation and bioinformatics

Sala Casartelli, viale Cavalotti 5, Como (Sala dei Nobel)

Organized by Ruggero Lanotte and Nicoletta Sabadini.

For further details see:
http://www.glauco.org/automatha/

Informatica Seminar, Vincenzo Manca, 21 June 2006

Vincenzo Manca, Professor of Computer Science
Universita' degli Studi di Verona

Titolo: "DNA e Membrane Computing": modelli di processi biomolecolari.

2:30pm Sala di Riunione
via Carloni 78

Abstract:
Il DNA Computing e' un campo di ricerca
introdotto da Adleman nel 1994, volto alla
soluzione di problemi NP completi mediante
tipiche operazioni biotecnologiche su codifiche
DNA dei dati. Il Membrane Computing e' un modello
di calcolo introdotto da Paun nel 1998, ispirato
dalla struttura cellulare. In entrambi i campi e'
emerso sempre di piu' l'interesse a utilizzare
gli strumenti formali di tali modelli nella
descrizione e nella analisi di fenomeni
biomolecalari (anche se a livelli diversi). Si
traccera' un quadro di queste problematiche,
accennando ad alcune ricerche e ad alcuni
risultati in cui la componente sperimentale e'
stata sviluppata in cooperazione con il
dipartimento di Patologia Generale
dell'Universita' di Verona.

Informatica Seminar

Dipartimento di Scienze della Cultura, Politiche e dell'Informazione
Informatica Seminar

3:30pm Wedneday 3rd May, Mauro Campanella (GARR),
Lo Stato di Internet e la Rete della Ricerca

Sala di Riuonione
via Carloni 78

RFC Walters