Wyniki wyszukiwania - BazTech

1

A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem

Halava V., Harju T., Sahla E.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

167--176

EN

We give a new simplified proof for undecidability of the Bi-Infinite Post Correspondence Problem (ℤPCP). We reduce the special case of the word problem of semi-Thue systems to ℤPCP.

2

Directed Overlap-inclusion Graphs as Representations of Ciliate Genes

Azimi S., Harju T., Langille M., Petre I., Rogojin V.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

29-44

EN

The simple intramolecular model for gene assembly in ciliates consists of three molecular operations based on local DNA manipulations. It was shown to predict correctly the assembly of all currently known ciliate gene patterns. Mathematical models in terms of signed permutations and signed strings proved limited in capturing some of the combinatorial details of the simple gene assembly process. A different formalization in terms of overlap-inclusion graphs, recently introduced by Brijder and Hoogeboom, proved well-suited to describe two of the three operations of the model and their combinatorial properties. We introduce in this paper an extension of the framework of Brijder and Hoogeboom in terms of directed overlap-inclusion graphs where more of the linear structure of the ciliate genes is described. We investigate a number of combinatorial properties of these graphs, including a necessary property in terms of forbidden induced subgraphs.

3

Undecidability in w-Regular Languages

Halava V., Harju T., Karhumäki J.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

119-125

EN

In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word a such that h(a) = g(a). In the general case this problem was shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of w-languages of the form Rw where R is a given regular language.

4

The Embedding Problem for Switching Classes of Graphs

Ehrenfeucht A., Hage J., Harju T., Rozenberg G.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 1

115-134

EN

In the context of graph transformation we look at the operation of switching, which can be viewed as a method for realizing global transformations of (group-labelled) graphs through local transformations of the vertices. In case vertices are given an identity, various relatively efficient algorithms exist for deciding whether a graph can be switched so that it contains some other graph, the query graph, as an induced subgraph. However, when considering graphs up to isomorphism, we immediately run into the graph isomorphism problem for which no efficient solution is known. Surprisingly enough however, in some cases the decision process can be simplified by transforming the query graph into a ``smaller'' graph without changing the answer. The main lesson learned is that the size of the query graph is not the dominating factor, but its cycle rank. Although a number of our results hold specifically for undirected, unlabelled graphs, we propose a more general framework and give many positive and negative results for more general cases, where the graphs are labelled with elements of a (finitely generated abelian) group.

5

Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

Hage J., Harju T., Welzl E.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 1

23--37

EN

In the context of graph transformations we look at the operation of switching, which can be viewed as a method for realizing global transformations of graphs through local transformations of the vertices. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation. Continuing the line of research in Ehrenfeucht, Hage, Harju and Rozenberg we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.

6

Undecidability in integer weighted finite automata

Halava V., Harju T.

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 1,2

189-200

EN

It is shown that the universe problem L(Ag) = A* is undecidable for 4-state finite automata A with integer weight function g on its transitions. This holds even in the case, where A is acyclic and the weighting g satisfies the unimodality condition. The language L(Ag) is defined as the set of words w for which there exists a path p of A having zero weight, that is, g(p) = 0.