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
Verifying Communicating Multi-pushdown Systems via Split-Width
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2014 (English)In: Automated Technology for Verification and Analysis, 2014, 1-17 p.Conference paper, Published paper (Refereed)
Abstract [en]

Communicating multi-pushdown systems model networks of multi-threaded recursive programs communicating via reliable FIFO channels. We extend the notion of split-width [8] to this setting, improving and simplifying the earlier definition. Split-width, while having the same power of clique-/tree-width, gives a divide-and-conquer technique to prove the bound of a class, thanks to the two basic operations, shuffle and merge, of the split-width algebra. We illustrate this technique on examples. We also obtain simple, uniform and optimal decision procedures for various verification problems parametrised by split-width.

Place, publisher, year, edition, pages
2014. 1-17 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8837
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:uu:diva-240882DOI: 10.1007/978-3-319-11936-6_1ISI: 000345585700005ISBN: 978-3-319-11936-6 (print)ISBN: 978-3-319-11935-9 (print)OAI: oai:DiVA.org:uu-240882DiVA: diva2:777668
Conference
12th International Symposium on Automated Technology for Verification and Analysis (ATVA), NOV 03-07, 2014, Sydney, AUSTRALIA
Available from: 2015-01-08 Created: 2015-01-08 Last updated: 2015-01-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Cyriac, Aiswarya

Search in DiVA

By author/editor
Cyriac, Aiswarya
By organisation
Computer Systems
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 368 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