Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

Equivalence of probabilis… - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

Equivalence of probabilistic μ-calculus and p-automata

Paper i proceeding
Författare Claudia Cauli
Nir Piterman
Publicerad i Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN 03029743
Publiceringsår 2017
Publicerad vid
Språk en
Ämneskategorier Datavetenskap (datalogi)

Sammanfattning

© Springer International Publishing AG 2017. An important characteristic of Kozen’s µ-calculus is its strong connection with parity alternating tree automata. Here, we show that the probabilistic µ-calculus µp-calculus and p-automata (parity alternating Markov chain automata) have an equally strong connection. Namely, for every µp-calculus formula we can construct a p-automaton that accepts exactly those Markov chains that satisfy the formula. For every p-automaton we can construct a µp-calculus formula satisfied in exactly those Markov chains that are accepted by the automaton. The translation in one direction relies on a normal form of the calculus and in the other direction on the usage of vectorial µp-calculus. The proofs use the game semantics of µp-calculus and automata to show that our translations are correct.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?