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

On Non-Periodic Solutions of Independent Systems of Word Equations Over Three Unknowns

Elena Czeizler, Juhani Karhumäki, On Non-Periodic Solutions of Independent Systems of Word Equations Over Three Unknowns. International Journal of Foundations of Computer Science 18(4), 873–897, 2007.

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

Abstract:

We investigate the open question asking whether there exist independent systems of three equations over three unknowns admitting non-periodic solutions, formulated in 1983 by Culik II and Karhumäki. In particular, we give a negative answer to this question for a large class of systems. More specifically, the question remains open only for a well specified class of systems. We also investigate systems of two equations over three unknowns for which we give necessary and sufficient conditions for admitting at most quasi-periodic solutions, i.e., solutions where the images of two unknowns are powers of a common word. In doing so, we also give a number of examples showing that these conditions represent a boundary point between systems admitting purely non-periodic solutions and those admitting at most quasi-periodic ones.

BibTeX entry:

@ARTICLE{jCzKa07b,
  title = {On Non-Periodic Solutions of Independent Systems of Word Equations Over Three Unknowns},
  author = {Czeizler, Elena and Karhumäki, Juhani},
  journal = {International Journal of Foundations of Computer Science},
  volume = {18},
  number = {4},
  pages = {873–897},
  year = {2007},
}

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

Publication Forum rating of this publication: level 2

Edit publication