• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the Power of Cooperating Morphisms via Reachability Problems

Juhani Karhumäki, On the Power of Cooperating Morphisms via Reachability Problems. International Journal of Foundations of Computer Science 20(5), 803–818, 2009.

http://dx.doi.org/10.1142/S0129054109006899

Abstract:

The goal of this presentation is to analyze the equality mechanism of cooperating morphisms of free monoids, and to point out how it can be used to define the reachability problems leading to important undecidability results and easy characterizations of recursively enumerable languages. In particular, we aim to show, which subconstructions are needed in such results. Moreover, we recall that in some cases the undecidability of the reachability is achieved although the sets of all reachable objects are simple, or more formally, regular languages.

BibTeX entry:

@ARTICLE{jKarhumaki_Juhani09a,
  title = {On the Power of Cooperating Morphisms via Reachability Problems},
  author = {Karhumäki, Juhani},
  journal = {International Journal of Foundations of Computer Science},
  volume = {20},
  number = {5},
  pages = {803–818},
  year = {2009},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication