Modular Trellises

Modular trellises are infinite two-dimensional words which are limits of developmental sequences of a very natural two-dimensional generalization of PDOL-systems.The original motivation to investigate modular trellises came from the area of systolic automata. Modular trellises represent there a class of very modular nonhomogeneous arrays of processors.Modular trellises are also a natural generalization of the Cobham’s /Co 72/ construction of uniform tag sequences based on iterating uniform morphisms.We first present here various properties of modular trellises and then we give various characterizations of them /in terms of sorting automata and in terms of fixpoints of morphisms and substitutions/. We discuss also the relation between modular and regular trellises /CGS 84/. Finally, decidability of various pattern occurrence problems is shown and decidability of the equivalence problem is discussed.