scientific article; zbMATH DE number 4094820

From MaRDI portal
Publication:3821587





[For the entire collection see Zbl 0658.00013.] Semisystolic systems with acyclic interconnection structures are investigated. Their underlying acyclic graphs represent partially ordered set diagrams of specific partially ordered sets. To understand the nature of such systems a new kind of polyautomata is introduced which we call pipeline-automata. The dynamical behavior of a pipeline-automaton resembles that of a pipeline. After providing the necessary order theoretic concepts the abilities of pipeline-automata with respect to equivalence, isomorphy and simulation are discussed. Because of their outstanding practical relevancy pipeline-automata with grid like interconnection structures are studied. To demonstrate the power of the formalism introduced, important results about semisystolic systems are transferred into the concepts of pipeline-automata. This provides also a new proof of the ``retiming lemma, which is shorter and even more comprehensible than the original one from \textit{Ch. E. Leiserson} and \textit{J. B. Saxe} [J. VLSI Comput. Syst. 1, 41-67 (1983; Zbl 0532.94015)].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3821587)