Decidability in syntactic control of interference

J. Laird

doi:10.1007/11523468

Decidability in syntactic control of interference

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

2 Citations (SciVal)

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 language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	Proceedings of the 32nd International Colloquim, ICALP 2005, Lisbon, Portugal, July 11-15, 2005
Editors	L. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi, M. Yung
Place of Publication	Berlin, Germany
Publisher	Springer Verlag
Pages	904-916
Number of pages	13
ISBN (Print)	9783540275800
DOIs	https://doi.org/10.1007/11523468
Publication status	Published - Jun 2005
Event	32nd International Colloquium on Automata, Languages and Programming, ICALP 2005 - Lisbon, Portugal Duration: 11 Jul 2005 → 15 Jul 2005

Publication series

Name	Theoretical Computer Science and General Issues
Number	Edition 1
Volume	3580

Conference

Conference	32nd International Colloquium on Automata, Languages and Programming, ICALP 2005
Country/Territory	Portugal
City	Lisbon
Period	11/07/05 → 15/07/05

ASJC Scopus subject areas

Computer Science (miscellaneous)

Access to Document

10.1007/11523468

http://dx.doi.org/10.1007/11523468

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

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

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

Laird, J 2005, Decidability in syntactic control of interference. in L Caires, GF 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. Theoretical Computer Science and General Issues, no. Edition 1, vol. 3580, Springer Verlag, Berlin, Germany, pp. 904-916, 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005, Lisbon, Portugal, 11/07/05. https://doi.org/10.1007/11523468

Laird J. Decidability in syntactic control of interference. In Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M, editors, Automata, Languages and Programming: Proceedings of the 32nd International Colloquim, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Berlin, Germany: Springer Verlag. 2005. p. 904-916. (Theoretical Computer Science and General Issues; Edition 1). doi: 10.1007/11523468

Laird, J. / Decidability in syntactic control of interference. Automata, Languages and Programming: Proceedings of the 32nd International Colloquim, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. editor / L. Caires ; G.F. Italiano ; L. Monteiro ; C. Palamidessi ; M. Yung. Berlin, Germany : Springer Verlag, 2005. pp. 904-916 (Theoretical Computer Science and General Issues; Edition 1).

@inproceedings{729d497124b84f7aacc3be1d9cbc1c6d,

title = "Decidability in syntactic control of interference",

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.",

author = "J. Laird",

year = "2005",

month = jun,

doi = "10.1007/11523468",

language = "English",

isbn = "9783540275800",

series = "Theoretical Computer Science and General Issues",

publisher = "Springer Verlag",

number = "Edition 1",

pages = "904--916",

editor = "L. Caires and G.F. Italiano and L. Monteiro and C. Palamidessi and M. Yung",

booktitle = "Automata, Languages and Programming",

note = "32nd International Colloquium on Automata, Languages and Programming, ICALP 2005 ; Conference date: 11-07-2005 Through 15-07-2005",

}

TY - GEN

T1 - Decidability in syntactic control of interference

AU - Laird, J.

PY - 2005/6

Y1 - 2005/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=26444480669&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1007/11523468

U2 - 10.1007/11523468

DO - 10.1007/11523468

M3 - Chapter in a published conference proceeding

AN - SCOPUS:26444480669

SN - 9783540275800

T3 - Theoretical Computer Science and General Issues

SP - 904

EP - 916

BT - Automata, Languages and Programming

A2 - Caires, L.

A2 - Italiano, G.F.

A2 - Monteiro, L.

A2 - Palamidessi, C.

A2 - Yung, M.

PB - Springer Verlag

CY - Berlin, Germany

T2 - 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005

Y2 - 11 July 2005 through 15 July 2005

ER -

Decidability in syntactic control of interference

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this