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

On Different Constrains on Three and Four Words

Elena Czeizler, Juhani Karhumäki, On Different Constrains on Three and Four Words. TUCS Technical Reports 787, Turku Centre for Computer Science, 2006.

Abstract:

In this paper we investigate the question whether there exist
independent systems of three word equations over three unknowns
possessing non-periodic solutions, formulated in 1983 in
[4]. 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 what happens when we consider chains of
equations such that each time we add a new one, the set of
solutions of the whole system strictly decreases. Thus, unlike in
the case of independence, now the order in which we choose the
equations becomes important. In this context we give some
reachable lower bounds for the size of such chains of equations
over three and four unknowns, respectively.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tCzKa06b,
  title = {On Different Constrains on Three and Four Words},
  author = {Czeizler, Elena and Karhumäki, Juhani},
  number = {787},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  ISBN = {952-12-1781-2},
}

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

Edit publication