Undecidability results for finite interactive systems

Alexandru Sofronia, Alexandru Popa, Gheorghe Stefanescu

Research output: Contribution to journalArticlepeer-review

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 - Dec 1 2009

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Undecidability results for finite interactive systems'. Together they form a unique fingerprint.

Cite this