Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
TCS Journal 2024 Journal Article
We present a construction to simulate Turing machines with 3 × 3 matrices over rationals. The correctness of simulation is guaranteed by testing that the matrices have integral elements during the simulation. This construction implies an undecidability result for a special identity problem for semigroups of 3 × 3 -matrices.
TCS Journal 2018 Journal Article
We show that it is undecidable whether or not an injective rational function (realized by a finite transducer) f: A ⁎ → A ⁎ has a fixed point. The proof applies undecidability of the Post's Correspondence Problem for injective morphisms. As a corollary we obtain that the existence of a fixed point of injective computable functions is undecidable.
TCS Journal 2017 Journal Article
In 1966 J. R. Isbell proved his algebraic Zig-Zag Theorem using a simple property of paths in a tiling of a plane rectangle. We prove here Isbell's lemma for more general tilings of plane rectangles.
TCS Journal 2015 Journal Article
We give new and simpler proof for the undecidability of the n-permutation Post Correspondence Problem that was originally proved by K. Ruohonen [10]. Our proof uses a recent result on deterministic semi-Thue systems according to which it is undecidable for a given deterministic semi-Thue system T and a word u whether or not there exists a nonempty cyclic derivation u → T + u in T.
TCS Journal 2009 Journal Article
We prove that for given morphisms g, h: { a 1, a 2, …, a n } → B ∗, it is decidable whether or not there exists a word w in the regular language a 1 ∗ a 2 ∗ ⋯ a n ∗ such that g ( w ) = h ( w ). In other words, we prove that the Post Correspondence Problem is decidable if the solutions are restricted to be from this special language. This yields a nice example of an undecidable problem in integral matrices which cannot be directly proved undecidable using the traditional reduction from the Post Correspondence Problem.
TCS Journal 2009 Journal Article
We prove that there exist infinitely many infinite overlap-free binary partial words containing at least one hole. Moreover, we show that these words cannot contain more than one hole and the only hole must occur either in the first or in the second position. We define that a partial word is k -overlap-free if it does not contain a factor of the form x y x y x where the length of x is at least k. We prove that there exist infinitely many 2-overlap-free binary partial words containing an infinite number of holes.
TCS Journal 2007 Journal Article
In the Post Correspondence Problem (PCP) an instance ( h, g ) consists of two morphisms h and g, and the problem is to determine whether or not there exists a nonempty word w such that h ( w ) = g ( w ). Here we prove that the PCP is decidable for instances with unique blocks using the decidability of the marked PCP. Also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. These results establish a new and larger class of decidable instances of the PCP, including the class of marked instances.
TCS Journal 2007 Journal Article
We consider words, i. e. strings over a finite alphabet together with a similarity relation induced by a compatibility relation on letters. This notion generalizes that of partial words. The theory of codes on combinatorics on words is revisited by defining ( R, S ) -codes for arbitrary similarity relations R and S. We describe an algorithm to test whether or not a finite set of words is an ( R, S ) -code. Coding properties of finite sets of words are explored by finding maximal and minimal relations with respect to relational codes.
TCS Journal 2002 Journal Article
We give a new proof for the decidability of the binary Post Correspondence Problem (PCP) originally proved in 1982 by Ehrenfeucht, Karhumäki and Rozenberg. Our proof is complete and somewhat shorter than the original proof although we use the same basic idea.
TCS Journal 2001 Journal Article
We show that the marked version of the Post Correspondence Problem, where the words on a list are required to differ in the first letter, is decidable. On the other hand, we prove that the PCP remains undecidable if we only require the words to differ in the first two letters. Thus we locate the decidability/undecidability-boundary between marked and 2-marked PCP.