Quadratic algebras, combinatorial physics and planar automata
Xavier Viennot
LaBRI, Universite Bordeaux.
06-02-12

---

Abstract

For certain quadratic algebras Q, we introduce the concept of Q-tableaux, which are certain combinatorial objects drawn on the square lattice. These tableaux are equivalent to notion of planar automaton. Planar automata is a new concept (not to be confused with cellular automata) which formalize the idea of recognizing certain "planar figures" drawn on a 2D lattice.

Examples are with two quadratic algebras well known in physics: the most simple Weyl-Heisenberg algebra defined by the commutation relation UD=DU+Id (creation-annihilation operators in quantum mechanics) and the so-called PASEP algebra defined by the relation DE=ED+E+D, in the physics of dynamical systems far from equilibrium. The associated Q-tableaux are respectively towers placements, permutations and the so-called alternating, tree-like and permutation tableaux. Other examples include non-crossing configurations of paths, tiling, plane partitions and alternating sign matrices.