Computing branching distances using quantitative games

DOI10.1007/978-3-030-32505-3_4MaRDI QIDQ2279111zbMATH OpenOpenAlexFDO

Authors Uli Fahrenberg, Axel Legay, Karin Quaas

Publication date 12 December 2019

Full work available at URL https://arxiv.org/abs/1910.08943

zbMATH Keywords

branching distancepath-building gamequantitative gamequantitative verification

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Applications of game theory (91A80)

Abstract: We lay out a general method for computing branching distances between labeled transition systems. We translate the quantitative games used for defining these distances to other, path-building games which are amenable to methods from the theory of quantitative games. We then show for all common types of branching distances how the resulting path-building games can be solved. In the end, we achieve a method which can be used to compute all branching distances in the linear-time--branching-time spectrum.

Recommendations

• Computing branching distances with quantitative games
• Distances for weighted transition systems: games and properties
• Automata, Languages and Programming
• The quantitative linear-time-branching-time spectrum
• The quantitative linear-time-branching-time spectrum

Cited in

(6)

• A game for linear-time-branching-time spectroscopy
• Dynamics of reputation in mobile agents systems and weighted timed automata
• Computing branching distances with quantitative games
• The quantitative linear-time-branching-time spectrum
• The quantitative linear-time-branching-time spectrum
• Distances for weighted transition systems: games and properties

This page was built for publication: Computing branching distances using quantitative games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279111)