A Transducer Approach to Coxeter Groups

✍ Scribed by F. du Cloux

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 466 KB
• Volume: 27
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1998.0254

✦ Synopsis

This paper represents an efficient way of implementing a (finite) Coxeter group W on a computer, through the use of a tower of special subgroups of W and the corresponding left cosets. We show how some results of Deodhar's may be interpreted in the language of finite state machines to produce a cascade of small transducers which handle the main "word processing" problems in the group. An algorithm is described for an efficient explicit construction of the relevant transducer tables starting from the Coxeter matrix of W . We also show (again interpreting a result of Deodhar's) that the Bruhat ordering on W presents a nice recursive structure in this implementation, leading to an effective enumeration of arbitrary Bruhat intervals.