Introducing equations in free semigroup

Speaker(s)

Robert Dąbrowski

Affiliation

Uniwersytet Warszawski

Date

Jan. 10, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Let be given a free monoid with a set of generators E whose cardinality is at least 2. We shall call elements of E 'letters' and elements of E* 'words'. Let also be given a set of 'unknowns'; disjoint with letters. A 'word expression' is defined recursively to be either a letter, an unknown or a nonempty finite sequence of word expressions. A 'word equation' is then of the form L=R where L, R are word expressions. A 'solution' to a word equation is any mapping from the unknowns into (possible empty) words which makes L and R identical words. The fundamental problem for equations in free monoids ('word equations') is to decide if a solution exists. The problem apparently had its source with Markov and remained open for a considerable period. The more general problem is finding a convenient description of all solutions. I will first present some fundamental constructions and results that allow to investigate word equations. Then I will summarize current results in respect to deciding solvability and finding solutions. I will focus on the cases with a fixed number of variables. Examples will follow.

---