Trace semantics via determinization

DOI10.1016/j.jcss.2014.12.005zbMath1327.68158OpenAlexW2098962004MaRDI QIDQ2341701

Ana Sokolova, Alexandra Silva, Bart Jacobs

Publication date: 28 April 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.12.005

zbMATH Keywords

coalgebraKleisli categoryEilenberg-Moore categorytrace semantics

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Categorical semantics of formal languages (18C50)

Related Items

Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies ⋮ Iterated covariant powerset is not a monad ⋮ ``Keep definition, change category -- a practical approach to state-based system calculi ⋮ Unnamed Item ⋮ Preservation and reflection of bisimilarity via invertible steps ⋮ Up-to techniques for behavioural metrics via fibrations ⋮ Coalgebraic trace semantics via forgetful logics ⋮ Up-To Techniques for Behavioural Metrics via Fibrations ⋮ Coalgebraic minimization of automata by initiality and finality ⋮ Duality of Equations and Coequations via Contravariant Adjunctions ⋮ Unnamed Item ⋮ Quantitative simulations by matrices ⋮ Long-term values in Markov decision processes, (co)algebraically ⋮ (in)finite trace equivalence of probabilistic transition systems ⋮ Steps and traces ⋮ Unnamed Item ⋮ Termination in Convex Sets of Distributions ⋮ Unnamed Item ⋮ Predicate and relation liftings for coalgebras with side effects: an application in coalgebraic modal logic ⋮ Coalgebraic semantics for nominal automata ⋮ Algebraic presentation of semifree monads

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Probabilistic logical characterization
• On coalgebras over algebras
• Notions of computation and monads
• Eilenberg--Moore algebras for stochastic relations
• Strong functors and monoidal monads
• Complete Iterativity for Algebras with Effects
• Trace Semantics via Determinization
• Coalgebraic Walks, in Quantum and Turing Computation
• Exemplaric Expressivity of Modal Logics
• A Spectrum of Behavioral Relations over LTSs on Probability Distributions
• Final Semantics for Decorated Traces
• Weighted Bisimulation in Linear Algebraic Form
• Characterising Testing Preorders for Finite Probabilistic Processes
• Testing Semantics: Connecting Processes and Process Logics
• Alternation
• Adjoint Lifting Theorems for Categories of Algebras
• Finite Automata Computing Real Functions
• Generalizing determinization from automata to coalgebras
• Mathematical Foundations of Computer Science 2004
• Scalars, Monads, and Categories
• Generic Trace Semantics via Coinduction
• Distributing probability over non-determinism
• Sound and Complete Axiomatization of Trace Semantics for Probabilistic Systems
• Logical Characterizations of Bisimulations for Discrete Probabilistic Systems
• Lifting theorems for Kleisli categories