BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this paper we propose a research programme for getting structural characterisations for 2-dimensional languages generated by self-assembling tiles. This is part of a larger programme on getting a formal foundation of parallel, interactive, distributed systems.
Two-dimensional patterns are used in many research areas in computer science, ranging from image processing to specification and verification of complex software systems (via scenarios). The contribution of this paper is twofold. First, we present the basis of a new formal representation of two-dimensional patterns based on contours and their compositions. Then, we present efficient algorithms to verify correctness of the contour-representation. Finally, we briefly discuss possible applications, in particular using them as a basic instrument in developing software tools for handling two dimensional words.
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.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.