Undecidability results for finite interactive systems

Alexandru Sofronia, Alexandru Popa, Gheorghe Stefanescu

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

2 Citations (Scopus)

Abstract

This paper is on the foundations of a recent approach to the design of massively parallel and interactive programming languages using rv-systems (interactive systems with registers and voices) and Agapia programming. It includes a few theoretical results on FISs (finite interactive systems), the underlying mechanism used for specifying control and interaction in these systems. First, we give a proof for the undecidability of the emptiness problem for FISs by reduction to the Post Correspondence Problem. Next, we use the proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recognized by a FIS. Finally, we present a simple proof of the equivalence between FISs and tile systems, making explicit that they precisely capture recognizable two-dimensional languages.

Original languageEnglish
Title of host publicationProceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008
Pages366-369
Number of pages4
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008 - Timisoara
Duration: Sep 26 2008Sep 29 2008

Other

Other2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008
CityTimisoara
Period9/26/089/29/08

Fingerprint

Tile
Computer programming languages

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Software

Cite this

Sofronia, A., Popa, A., & Stefanescu, G. (2008). Undecidability results for finite interactive systems. In Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008 (pp. 366-369). [5204840] https://doi.org/10.1109/SYNASC.2008.42

Undecidability results for finite interactive systems. / Sofronia, Alexandru; Popa, Alexandru; Stefanescu, Gheorghe.

Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008. 2008. p. 366-369 5204840.

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

Sofronia, A, Popa, A & Stefanescu, G 2008, Undecidability results for finite interactive systems. in Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008., 5204840, pp. 366-369, 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008, Timisoara, 9/26/08. https://doi.org/10.1109/SYNASC.2008.42
Sofronia A, Popa A, Stefanescu G. Undecidability results for finite interactive systems. In Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008. 2008. p. 366-369. 5204840 https://doi.org/10.1109/SYNASC.2008.42
Sofronia, Alexandru ; Popa, Alexandru ; Stefanescu, Gheorghe. / Undecidability results for finite interactive systems. Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008. 2008. pp. 366-369
@inproceedings{880fcde2218748d78d8bc8d4cfb73fbe,
title = "Undecidability results for finite interactive systems",
abstract = "This paper is on the foundations of a recent approach to the design of massively parallel and interactive programming languages using rv-systems (interactive systems with registers and voices) and Agapia programming. It includes a few theoretical results on FISs (finite interactive systems), the underlying mechanism used for specifying control and interaction in these systems. First, we give a proof for the undecidability of the emptiness problem for FISs by reduction to the Post Correspondence Problem. Next, we use the proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recognized by a FIS. Finally, we present a simple proof of the equivalence between FISs and tile systems, making explicit that they precisely capture recognizable two-dimensional languages.",
author = "Alexandru Sofronia and Alexandru Popa and Gheorghe Stefanescu",
year = "2008",
doi = "10.1109/SYNASC.2008.42",
language = "English",
isbn = "9780769535234",
pages = "366--369",
booktitle = "Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008",

}

TY - GEN

T1 - Undecidability results for finite interactive systems

AU - Sofronia, Alexandru

AU - Popa, Alexandru

AU - Stefanescu, Gheorghe

PY - 2008

Y1 - 2008

N2 - This paper is on the foundations of a recent approach to the design of massively parallel and interactive programming languages using rv-systems (interactive systems with registers and voices) and Agapia programming. It includes a few theoretical results on FISs (finite interactive systems), the underlying mechanism used for specifying control and interaction in these systems. First, we give a proof for the undecidability of the emptiness problem for FISs by reduction to the Post Correspondence Problem. Next, we use the proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recognized by a FIS. Finally, we present a simple proof of the equivalence between FISs and tile systems, making explicit that they precisely capture recognizable two-dimensional languages.

AB - This paper is on the foundations of a recent approach to the design of massively parallel and interactive programming languages using rv-systems (interactive systems with registers and voices) and Agapia programming. It includes a few theoretical results on FISs (finite interactive systems), the underlying mechanism used for specifying control and interaction in these systems. First, we give a proof for the undecidability of the emptiness problem for FISs by reduction to the Post Correspondence Problem. Next, we use the proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recognized by a FIS. Finally, we present a simple proof of the equivalence between FISs and tile systems, making explicit that they precisely capture recognizable two-dimensional languages.

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

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

U2 - 10.1109/SYNASC.2008.42

DO - 10.1109/SYNASC.2008.42

M3 - Conference contribution

SN - 9780769535234

SP - 366

EP - 369

BT - Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2008

ER -