Full abstraction for fair testing in CCS

DOI10.1007/978-3-642-40206-7_14zbMATH Open1310.68149arXiv1305.6184OpenAlexW1890822632MaRDI QIDQ2848947FDOQ2848947

Authors: Tom Hirschowitz 

Publication date: 13 September 2013

Published in: Algebra and Coalgebra in Computer Science (Search for Journal in Brave)

Abstract: In previous work with Pous, we defined a semantics for CCS which may both be viewed as an innocent presheaf semantics and as a concurrent game semantics. It is here proved that a behavioural equivalence induced by this semantics on CCS processes is fully abstract for fair testing equivalence. The proof relies on a new algebraic notion called playground, which represents the 'rule of the game'. From any playground, two languages, equipped with labelled transition systems, are derived, as well as a strong, functional bisimulation between them.

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

Recommendations

• Full abstraction for fair testing in CCS (expanded version)
• scientific article; zbMATH DE number 1231450
• Innocent strategies as presheaves and interactive equivalences for CCS
• scientific article; zbMATH DE number 3900141
• A fully abstract semantics for concurrent constraint programming

zbMATH Keywords

programming languagescategorical semanticsconcurrencygame semanticsprocess algebrapresheaf semantics

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Abstract data types; algebraic specification (68Q65) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (3)

• Strategies as concurrent processes
• Innocent strategies as presheaves and interactive equivalences for CCS
• Full abstraction for fair testing in CCS (expanded version)

Uses Software

• CompCert

This page was built for publication: Full abstraction for fair testing in CCS

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