Interface simulation distances

DOI10.1016/J.TCS.2014.08.019zbMATH Open1303.68076arXiv1210.2450OpenAlexW2049708124MaRDI QIDQ477211FDOQ477211

Authors: Pavol Černý, Martin Chmelík, Thomas A. Henzinger, Arjun Radhakrishna 

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a distance for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intuitively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, and that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.

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

Recommendations

• Interface simulation distances
• Simulation distances
• Simulation distances
• Quantitative simulation games
• Metrics for weighted transition systems: axiomatization and complexity

zbMATH Keywords

gamesquantitative analysisalternating simulation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of game theory (91A80) Games involving graphs (91A43)

Cites Work

• The complexity of mean payoff games on graphs
• Statecharts: a visual formalism for complex systems
• Simulation distances
• Metrics for labelled Markov processes
• Title not available (Why is that?)
• Modal I/O Automata for Interface and Product Line Theories
• Generalized mean-payoff and energy games
• Game Refinement Relations and Metrics
• Title not available (Why is that?)
• Simulation distances
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interface simulation distances
• An introduction to metric semantics: Operational and denotational models for programming and specification languages

Cited In (5)

• Simulation distances
• Simulation distances
• Quantitative simulation games
• Interface simulation distances
• Semantic distance between specifications

This page was built for publication: Interface simulation distances

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