Laura Ciobanu Radomirovic – The language complexity of solutions of equations in free semigroups and groups (21 June, 2017)
by Rob Stewart • September 8, 2017 • DSG Research Seminars: Logic and Programming Languages
We show that, given a word equation over a finitely generated free group (or semigroup), the set of all solutions in reduced words forms an EDT0L language. In particular, it is an indexed language in the sense of Aho. This is joint work with Murray Elder and Volker Diekert.