Computer Science – Formal Languages and Automata Theory
Scientific paper
2009-12-31
Romanian Journal of Information Science and Technology, Volume 12 (2009), pp. 265-279
Computer Science
Formal Languages and Automata Theory
Scientific paper
A new approach to the design of massively parallel and interactive 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 problem 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 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.
Popa Alexandru
Sofronia Alexandru
Stefanescu Gheorghe
No associations
LandOfFree
Undecidability Results for Finite Interactive Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Undecidability Results for Finite Interactive Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Undecidability Results for Finite Interactive Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-104704