Decidability in syntactic control of interference

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

We investigate the decidability of observational equivalence and approximation in "Syntactic Control of Interference" (SCI). By associating denotations of terms in an inequationally fully abstract model of unitary basic SCI with multitape finite state automata, we show that observational approximation is not decidable (even at first order), but that observational equivalence is decidable for all terms. We then consider the same problems for basic SCI extended with non-local control in the form of backwards jumps. We show that both observational approximation and observational equivalence are decidable in this language by describing a fully abstract games model in which strategies are regular languages.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publicationProceedings of the 32nd International Colloquim, ICALP 2005, Lisbon, Portugal, July 11-15, 2005
EditorsL. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi, M. Yung
Place of PublicationBerlin, Germany
PublisherSpringer Verlag
Pages904-916
Number of pages13
ISBN (Print)9783540275800
DOIs
Publication statusPublished - Jun 2005
Event32nd International Colloquium on Automata, Languages and Programming, ICALP 2005 - Lisbon, Portugal
Duration: 11 Jul 200515 Jul 2005

Publication series

NameTheoretical Computer Science and General Issues
NumberEdition 1
Volume3580

Conference

Conference32nd International Colloquium on Automata, Languages and Programming, ICALP 2005
CountryPortugal
CityLisbon
Period11/07/0515/07/05

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Fingerprint Dive into the research topics of 'Decidability in syntactic control of interference'. Together they form a unique fingerprint.

  • Cite this

    Laird, J. (2005). Decidability in syntactic control of interference. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, & M. Yung (Eds.), Automata, Languages and Programming: Proceedings of the 32nd International Colloquim, ICALP 2005, Lisbon, Portugal, July 11-15, 2005 (pp. 904-916). (Theoretical Computer Science and General Issues; Vol. 3580, No. Edition 1). Springer Verlag. https://doi.org/10.1007/11523468