1986 | OriginalPaper | Chapter
Modular Trellises
Authors : A. Černý, J. Gruska
Published in: The Book of L
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.