Inscriere cercetatori

Premii Ad Astra

premii Ad Astra

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: http://premii.ad-astra.ro/. Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la cristian.presura@gmail.com

Undecidability Results for Finite Interactive Systems

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

Autori: Alexandru Sofronia, Alexandru Popa, Gheorghe Stefanescu

Editorial: Romanian Journal of Information Science and Technology, 12 (2), p.265 - 279, 2009.

Rezumat:

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.

Cuvinte cheie: Finite Interactive Systems, tile systems, PCP, undecidability

URL: http://arxiv.org/abs/1001.0143

Undecidability Results for Finite Interactive Systems

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

Autori: Alexandru Sofronia, Alexandru Popa, Gheorghe Stefanescu

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

Rezumat:

This paper is on the foundations of a recent approach to the design of massively parallel and interactiveprogramming 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.

Cuvinte cheie: Finite Interactive Systems, tile systems, PCP, undecidability

URL: http://doi.ieeecomputersociety.org/10.1109/SYNASC.2008.42