Decidability in syntactic control of interference

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

2 Citations (SciVal)


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
Number of pages13
ISBN (Print)9783540275800
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


Conference32nd International Colloquium on Automata, Languages and Programming, ICALP 2005

ASJC Scopus subject areas

  • Computer Science (miscellaneous)


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

Cite this