A classification of the expressive power of well-structured transition systems.

Abdulla, P; Delzanno, G.; BEGIN L, Van

doi:10.1016/j.ic.2010.11.003

CINECA IRIS Institutional Research Information System

IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.

We compare the expressive power of a class of well-structured transition systems that includes relational automata (extensions of), Petri nets, lossy channel systems, constrained multiset rewriting systems, and data nets. For each one of these models we study the class of languages generated by labeled transition systems describing their semantics. We consider here two types of accepting conditions: coverability and reachability of a fixed a priori configuration. In both cases we obtain a strict hierarchy in which constrained multiset rewriting systems is the most expressive model.

Scheda prodotto non validato

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

SFX

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11567/255676

Titolo:	A classification of the expressive power of well-structured transition systems.
Autori interni:	DELZANNO, GIORGIO
Data di pubblicazione:	2011
Rivista:	INFORMATION AND COMPUTATION
Abstract:	We compare the expressive power of a class of well-structured transition systems that includes relational automata (extensions of), Petri nets, lossy channel systems, constrained multiset rewriting systems, and data nets. For each one of these models we study the class of languages generated by labeled transition systems describing their semantics. We consider here two types of accepting conditions: coverability and reachability of a fixed a priori configuration. In both cases we obtain a strict hierarchy in which constrained multiset rewriting systems is the most expressive model.
Handle:	http://hdl.handle.net/11567/255676
Appare nelle tipologie:	01.01 - Articolo su rivista

File in questo prodotto:

Non ci sono file associati a questo prodotto.

Citazioni

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.