The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids (Q798007): Difference between revisions

The author's goal is to survey recent results obtained on the Ehrenfeucht Conjecture: For each language L over a finite alphabet \(\Sigma\) there exists a finite subset F of L such that each pair (g,h) of morphisms on \(\Sigma^ x\) the equation \(g(x)=h(x)\) holds for all x in L if and only if it holds for all x in F. - The author discusses an interpretation of the Ehrenfeucht Conjecture in terms of equations in free monoids. Namely, the conjecture is equivalent to the following statement: Each system of equations over a finitely generated monoid and with a finite number of variables has an equivalent finite subsystem. - In the sequel the author discusses the connection of the Ehrenfeucht Conjecture with the so-called HDOL sequence equivalence problems and he turns to consider when the conjecture is known to hold. The next section devoted to establishing to Ehrenfeucht Conjecture for all languages over a binary alphabet. The author concludes that the Ehrenfeucht Conjecture is a well motivated and fundamental problem not only from the point of view of formal languages but also from the point of view of free monoids as a whole.