Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Verification of Dynamic Register Automata
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. (Algorithmic Program Verification)
2014 (Engelska)Ingår i: Leibniz International Proceedings in Informatics: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014), 2014Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

We consider the verification problem for Dynamic Register Automata (Dra). Dra extend classical register automata by process creation. In this setting, each process is equipped with a finite number of registers in which the process IDs of other processes can be stored. A process can communicate with processes whose IDs are stored in its registers and can send them the content of its registers. The state reachability problem asks whether a Dra reaches a configuration where at least one process is in an error state. We first show that this problem is in general undecidable. This result holds even when we restrict the analysis to configurations where the maximal length of the simple paths in their underlying (un)directed communication graphs are bounded by some constant. Then we introduce the model of degenerative Dra which allows non-deterministic reset of the registers. We prove that for every given Dra, its corresponding degenerative one has the same set of reachable states. While the state reachability of a degenerative Dra remains undecidable, we show that the problem becomes decidable with nonprimitive-recursive complexity when we restrict the analysis to strongly bounded configurations, i.e. configurations whose underlying undirected graphs have bounded simple paths. Finally, we consider the class of strongly safe Dra, where all the reachable configurations are assumed to be strongly bounded. We show that for strongly safe Dra, the state reachability problem becomes decidable. 

Ort, förlag, år, upplaga, sidor
2014.
Nyckelord [en]
Register Automata, State Reachability, Formal Verification
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datavetenskap
Identifikatorer
URN: urn:nbn:se:uu:diva-237854OAI: oai:DiVA.org:uu-237854DiVA: diva2:769210
Konferens
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India, December 15–17 2014.
Projekt
ProFuNUPMARC
Tillgänglig från: 2014-12-05 Skapad: 2014-12-05 Senast uppdaterad: 2014-12-17Bibliografiskt granskad

Open Access i DiVA

fulltext(1434 kB)145 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1434 kBChecksumma SHA-512
9357e8bc51b8172074a14b0f3c85d1556f6f411cdfeacc84868869dafc9e5acd481b85ef7e451e3d5dd5d70c11b428d5ce9bc5cf1fff8b963bcc206e0a582282
Typ fulltextMimetyp application/pdf

Sök vidare i DiVA

Av författaren/redaktören
Abdulla, Parosh AzizAtig, Mohamed FaouziRezine, Othmane
Av organisationen
Datorteknik
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 145 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

Totalt: 587 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf