Quadratic algebras, combinatorial physics and planar automata Xavier Viennot LaBRI, Universite Bordeaux. 060212 Abstract For certain quadratic algebras Q, we introduce the concept of Qtableaux, 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 WeylHeisenberg algebra defined by the commutation relation UD=DU+Id (creationannihilation operators in quantum mechanics) and the socalled PASEP algebra defined by the relation DE=ED+E+D, in the physics of dynamical systems far from equilibrium. The associated Qtableaux are respectively towers placements, permutations and the socalled alternating, treelike and permutation tableaux. Other examples include noncrossing configurations of paths, tiling, plane partitions and alternating sign matrices.
