--- _id: '3353' abstract: - lang: eng text: 'Compositional theories are crucial when designing large and complex systems from smaller components. In this work we propose such a theory for synchronous concurrent systems. Our approach follows so-called interface theories, which use game-theoretic interpretations of composition and refinement. These are appropriate for systems with distinct inputs and outputs, and explicit conditions on inputs that must be enforced during composition. Our interfaces model systems that execute in an infinite sequence of synchronous rounds. At each round, a contract must be satisfied. The contract is simply a relation specifying the set of valid input/output pairs. Interfaces can be composed by parallel, serial or feedback composition. A refinement relation between interfaces is defined, and shown to have two main properties: (1) it is preserved by composition, and (2) it is equivalent to substitutability, namely, the ability to replace an interface by another one in any context. Shared refinement and abstraction operators, corresponding to greatest lower and least upper bounds with respect to refinement, are also defined. Input-complete interfaces, that impose no restrictions on inputs, and deterministic interfaces, that produce a unique output for any legal input, are discussed as special cases, and an interesting duality between the two classes is exposed. A number of illustrative examples are provided, as well as algorithms to compute compositions, check refinement, and so on, for finite-state interfaces.' article_number: '14' author: - first_name: Stavros full_name: Tripakis, Stavros last_name: Tripakis - first_name: Ben full_name: Lickly, Ben last_name: Lickly - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Edward full_name: Lee, Edward last_name: Lee citation: ama: Tripakis S, Lickly B, Henzinger TA, Lee E. A theory of synchronous relational interfaces. ACM Transactions on Programming Languages and Systems (TOPLAS). 2011;33(4). doi:10.1145/1985342.1985345 apa: Tripakis, S., Lickly, B., Henzinger, T. A., & Lee, E. (2011). A theory of synchronous relational interfaces. ACM Transactions on Programming Languages and Systems (TOPLAS). ACM. https://doi.org/10.1145/1985342.1985345 chicago: Tripakis, Stavros, Ben Lickly, Thomas A Henzinger, and Edward Lee. “A Theory of Synchronous Relational Interfaces.” ACM Transactions on Programming Languages and Systems (TOPLAS). ACM, 2011. https://doi.org/10.1145/1985342.1985345. ieee: S. Tripakis, B. Lickly, T. A. Henzinger, and E. Lee, “A theory of synchronous relational interfaces,” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 33, no. 4. ACM, 2011. ista: Tripakis S, Lickly B, Henzinger TA, Lee E. 2011. A theory of synchronous relational interfaces. ACM Transactions on Programming Languages and Systems (TOPLAS). 33(4), 14. mla: Tripakis, Stavros, et al. “A Theory of Synchronous Relational Interfaces.” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 33, no. 4, 14, ACM, 2011, doi:10.1145/1985342.1985345. short: S. Tripakis, B. Lickly, T.A. Henzinger, E. Lee, ACM Transactions on Programming Languages and Systems (TOPLAS) 33 (2011). date_created: 2018-12-11T12:02:51Z date_published: 2011-07-01T00:00:00Z date_updated: 2021-01-12T07:42:52Z day: '01' ddc: - '000' - '005' department: - _id: ToHe doi: 10.1145/1985342.1985345 ec_funded: 1 file: - access_level: open_access checksum: 5d44a8aa81e33210649beae507602138 content_type: application/pdf creator: system date_created: 2018-12-12T10:16:45Z date_updated: 2020-07-14T12:46:09Z file_id: '5235' file_name: IST-2012-85-v1+1_A_theory_of_synchronous_relational_interfaces.pdf file_size: 775662 relation: main_file file_date_updated: 2020-07-14T12:46:09Z has_accepted_license: '1' intvolume: ' 33' issue: '4' language: - iso: eng month: '07' oa: 1 oa_version: Submitted Version project: - _id: 25EFB36C-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '215543' name: COMponent-Based Embedded Systems design Techniques - _id: 25F1337C-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '214373' name: Design for Embedded Systems - _id: 25EE3708-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '267989' name: Quantitative Reactive Modeling - _id: 25F5A88A-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Moderne Concurrency Paradigms publication: ACM Transactions on Programming Languages and Systems (TOPLAS) publication_status: published publisher: ACM publist_id: '3263' pubrep_id: '85' quality_controlled: '1' scopus_import: 1 status: public title: A theory of synchronous relational interfaces type: journal_article user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 volume: 33 year: '2011' ...