Global ETD Search

21	LTCS-Report Technische Universität Dresden 17 March 2022 (has links) This series consists of technical reports produced by the members of the Chair for Automata Theory at TU Dresden. The purpose of these reports is to provide detailed information (e.g., formal proofs, worked out examples, experimental results, etc.) for articles published in conference proceedings with page limits. The topics of these reports lie in different areas of the overall research agenda of the chair, which includes Logic in Computer Science, symbolic AI, Knowledge Representation, Description Logics, Automated Deduction, and Automata Theory and its applications in the other fields. info:eu-repo/classification/ddc/004 ddc:004
22	Categorical semantics and composition of tree transducers / Kategorielle Semantik und Komposition von Baumübersetzern Jürgensen, Claus 28 December 2004 (has links) (PDF) In this thesis we see two new approaches to compose tree transducers and more general to fuse functional programs. The first abroach is based on initial algebras. We prove a new variant of the acid rain theorem for mutually recursive functions where the build function is substituted by a concrete functor. Moreover, we give a symmetric form (i.e. consumer and producer have the same syntactic form) of our new acid rain theorem where fusion is composition in a category and thus in particular associative. Applying this to compose top-down tree transducers yields the same result (on a syntactic level) as the classical top-down tree transducer composition. The second approach is based on free monads and monad transformers. In the same way as monoids are used in the theory of character string automata, we use monads in the theory of tree transducers. We generalize the notion of a tree transducer defining the monadic transducer, and we prove an according fusion theorem. Moreover, we prove that homomorphic monadic transducers are semantically equivalent. The latter makes it possible to compose syntactic classes of tree transducers (or particular functional programs) by simply composing endofunctors. Baumübersetzer Deforestation Fusion Haskel Monade Monadentransformer Programmtransformation funktionale Sprache Haskell deforestation functional program fusion monad monad transformer program transformation tree transducer ddc:004 rvk:ST 140 Formale Semantik Funktionale Programmiersprache Kategorientheorie Programmtransformation
23	Categorical semantics and composition of tree transducers Jürgensen, Claus 30 January 2004 (has links) In this thesis we see two new approaches to compose tree transducers and more general to fuse functional programs. The first abroach is based on initial algebras. We prove a new variant of the acid rain theorem for mutually recursive functions where the build function is substituted by a concrete functor. Moreover, we give a symmetric form (i.e. consumer and producer have the same syntactic form) of our new acid rain theorem where fusion is composition in a category and thus in particular associative. Applying this to compose top-down tree transducers yields the same result (on a syntactic level) as the classical top-down tree transducer composition. The second approach is based on free monads and monad transformers. In the same way as monoids are used in the theory of character string automata, we use monads in the theory of tree transducers. We generalize the notion of a tree transducer defining the monadic transducer, and we prove an according fusion theorem. Moreover, we prove that homomorphic monadic transducers are semantically equivalent. The latter makes it possible to compose syntactic classes of tree transducers (or particular functional programs) by simply composing endofunctors. info:eu-repo/classification/ddc/004 ddc:004

Page generated in 0.097 seconds