The Theory of Traces for Systems with Nondeterminism and Probability
Autor: | Ana Sokolova, Valeria Vignudelli, Filippo Bonchi |
---|---|
Přispěvatelé: | University of Pisa - Università di Pisa, University of Salzburg, Université de Lyon, Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Claude Bernard Lyon 1 (UCBL), ANR-16-CE25-0011,REPAS,Des systèmes logiciels fiables et conscients des données privées, via les métriques de bisimulation(2016), European Project: 678157,H2020,ERC-2015-STG,CoVeCe(2016), École normale supérieure de Lyon (ENS de Lyon), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Valeria, Vignudelli, Des systèmes logiciels fiables et conscients des données privées, via les métriques de bisimulation - - REPAS2016 - ANR-16-CE25-0011 - AAPG2016 - VALID, Coinduction for Verification and Certification - CoVeCe - - H20202016-04-01 - 2021-03-31 - 678157 - VALID |
Jazyk: | angličtina |
Rok vydání: | 2019 |
Předmět: |
[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO]
Computer science Semantics (computer science) Probabilistic logic [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] 0102 computer and information sciences 02 engineering and technology 01 natural sciences Automaton Nondeterministic algorithm Algebra 010201 computation theory & mathematics Computer Science::Logic in Computer Science 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algebra over a field Algebraic number TRACE (psycholinguistics) |
Zdroj: | Logic in Computer Science (LICS) 2019 Logic in Computer Science (LICS) 2019, Jun 2019, Vancouver, Canada LICS |
Popis: | International audience; This paper studies trace-based equivalences for systems combining nondeterministic and probabilistic choices. We show how trace semantics for such processes can be recovered by instantiating a coalgebraic construction known as the generalised powerset construction. We characterise and compare the resulting semantics to known definitions of trace equivalences appearing in the literature. Most of our results are based on the exciting interplay between monads and their presentations via algebraic theories. |
Databáze: | OpenAIRE |
Externí odkaz: |