uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A classification of the expressive power of well-structured transition systems
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology. (Algorithmic Program Verification)
2011 (English)In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 209, no 3, 248-279 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2011. Vol. 209, no 3, 248-279 p.
National Category
Computer Science Computer Engineering
Identifiers
URN: urn:nbn:se:uu:diva-159329DOI: 10.1016/j.ic.2010.11.003ISI: 000287382300002OAI: oai:DiVA.org:uu-159329DiVA: diva2:444177
Projects
apvwqo
Available from: 2011-09-28 Created: 2011-09-28 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Abdulla, Parosh Aziz

Search in DiVA

By author/editor
Abdulla, Parosh Aziz
By organisation
Department of Information Technology
In the same journal
Information and Computation
Computer ScienceComputer Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 705 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf