A linear-time branching-time perspective on interface automata
Open Access
- 6 May 2020
- journal article
- research article
- Published by Springer Nature in Acta Informatica
- Vol. 57 (3-5) , 513-550
Abstract
Over the past two decades, de Alfaro and Henzinger’s interface automata (IA) have become a popular formal framework for the component-based specification of concurrent systems. IA’s parallel composition assumes that a component may wait on inputs but never on outputs, implying that an output must be consumed immediately or a communication error occurs. By now, the literature contains a number of semantics for IA: linear-time semantics based on traces observing communication errors, quiescence and/or divergence, as well as branching-time semantics based on alternating simulation. This article surveys these semantics from Rob van Glabbeek’s linear-time branching-time perspective, which does not consider settings with communication errors. We shed light onto the subtleties implied by IA’s pruning of all behaviour that might lead a component to autonomously enter an error state, and investigate when exactly de Alfaro and Henzinger’s restriction of input-determinism is needed. In addition, we introduce several new semantics for IA, in particular the linear-time ready semantics and the branching-time ready simulation.Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (VO 615/12-2, LU 1748/3-2)
This publication has 35 references indexed in Scilit:
- Multiparty asynchronous session typesACM SIGPLAN Notices, 2008
- Component refinement and CSC-solving for STG decompositionTheoretical Computer Science, 2007
- Concurrency and automata on infinite sequences2005
- Interface automataACM SIGSOFT Software Engineering Notes, 2001
- Branching time and abstraction in bisimulation semanticsJournal of the ACM, 1996
- Arbiters: an exercise in specifying and decomposing asynchronously communicating componentsScience of Computer Programming, 1992
- Observation equivalence as a testing equivalenceTheoretical Computer Science, 1987
- Specification-oriented semantics for Communicating ProcessesActa Informatica, 1986
- A Theory of Communicating Sequential ProcessesJournal of the ACM, 1984
- Testing equivalences for processesTheoretical Computer Science, 1984