Undecidability results for finite interactive systems

Alexandru Sofronia, Alexandru Popa, Gheorghe Stefanescu

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

A new approach to the design of massively parallel and in- teractive programming languages has been recently proposed using rv-systems (interactive systems with registers and voices) and Agapia programming. In this paper we present 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 prob- lem for FISs, by reduction to the Post Correspondence Problem. Next, we use the construction in this proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recog- nized 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
Pages (from-to)265-279
Number of pages15
JournalRomanian Journal of Information Science and Technology
Volume12
Issue number2
Publication statusPublished - 2009
Externally publishedYes

Fingerprint

Tile
Computer programming languages

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

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

In: Romanian Journal of Information Science and Technology, Vol. 12, No. 2, 2009, p. 265-279.

Research output: Contribution to journalArticle

Sofronia, A, Popa, A & Stefanescu, G 2009, 'Undecidability results for finite interactive systems', Romanian Journal of Information Science and Technology, vol. 12, no. 2, pp. 265-279.
Sofronia, Alexandru ; Popa, Alexandru ; Stefanescu, Gheorghe. / Undecidability results for finite interactive systems. In: Romanian Journal of Information Science and Technology. 2009 ; Vol. 12, No. 2. pp. 265-279.
@article{f47c5a5dc67a4731a2fafde6076806d7,
title = "Undecidability results for finite interactive systems",
abstract = "A new approach to the design of massively parallel and in- teractive programming languages has been recently proposed using rv-systems (interactive systems with registers and voices) and Agapia programming. In this paper we present 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 prob- lem for FISs, by reduction to the Post Correspondence Problem. Next, we use the construction in this proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recog- nized 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 = "2009",
language = "English",
volume = "12",
pages = "265--279",
journal = "Romanian Journal of Information Science and Technology",
issn = "1453-8245",
publisher = "Publishing House of the Romanian Academy",
number = "2",

}

TY - JOUR

T1 - Undecidability results for finite interactive systems

AU - Sofronia, Alexandru

AU - Popa, Alexandru

AU - Stefanescu, Gheorghe

PY - 2009

Y1 - 2009

N2 - A new approach to the design of massively parallel and in- teractive programming languages has been recently proposed using rv-systems (interactive systems with registers and voices) and Agapia programming. In this paper we present 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 prob- lem for FISs, by reduction to the Post Correspondence Problem. Next, we use the construction in this proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recog- nized 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 - A new approach to the design of massively parallel and in- teractive programming languages has been recently proposed using rv-systems (interactive systems with registers and voices) and Agapia programming. In this paper we present 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 prob- lem for FISs, by reduction to the Post Correspondence Problem. Next, we use the construction in this proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recog- nized 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=84864376376&partnerID=8YFLogxK

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

M3 - Article

VL - 12

SP - 265

EP - 279

JO - Romanian Journal of Information Science and Technology

JF - Romanian Journal of Information Science and Technology

SN - 1453-8245

IS - 2

ER -