Wyniki wyszukiwania - BazTech

1

k-Abelian Equivalence and Rationality

Cassaigne J., Karhumäki J., Puzynina S., Whiteland M. A.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

65--94

EN

Two words u and v are said to be k-abelian equivalent if, for each word x of length at most k, the number of occurrences of x as a factor of u is the same as for v. We study some combinatorial properties of k-abelian equivalence classes. Our starting point is a characterization of k-abelian equivalence by rewriting, so-called k-switching. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k-abelian equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is ℕ-rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size.

2

The Unique Decipherability in the Monoid of Regular Languages is Undecidable

Karhumäki J., Saarela A.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

197-200

EN

We show by a simple reduction that the unique decipherability problem in the language monoid of regular languages over a non-unary alphabet is undecidable.

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

Defect theorems for trees

Karhumäki J., Mantaci S.

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 1,2

119-133

EN

We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However as we show, the prefix rank forms an exception.

5

Arto Salomaa : publications by Arto Salomaa

Karhumäki J., Mateescu A., Rozenberg G.

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 1,2

11-11