Automaticity, finite complete rewriting systems, and finite derivation type for homogeneous monoids.

Room FC1.030, DMat-FCUP
Friday, 17 January, 2014 - 14:30

 

In recent work with Gray and Malheiro, I proved that finite-rank plactic monoids admit presentations via finite complete rewriting systems and are biautomatic. This seminar will discuss the next stage of this work. First, I will discuss how similar techniques using rather different tricks (sometimes exploiting connections with combinatorics) can be used to prove that other important homogeneous monoids (such as finite-rank Chinese, hypoplactic, and Sylvester monoids) are automatic and can be presented via complete rewriting systems. Second, I will consider the relationship, within the class of homogeneous monoids, of the properties of automaticity, being presented via a finite complete rewriting system, and finite derivation type. (Being presented via a finite complete rewriting system always implies finite derivation type, but otherwise these properties are independent for general monoids.)

Speaker: 

Alan Cain (CAUL)
Error | CMUP

Error

The website encountered an unexpected error. Please try again later.