The Experts below are selected from a list of 225 Experts worldwide ranked by ideXlab platform
Lawrence S Moss - One of the best experts on this subject based on the ideXlab platform.
-
Corrigendum to: “The category theoretic solution of Recursive Program schemes” [Theoret. Comput. Sci. 366 (2006) 3–59]
Theoretical Computer Science, 2020Co-Authors: Stefan Milius, Lawrence S MossAbstract:AbstractThis is a corrigendum for our paper [S. Milius, L.S. Moss, The category theoretic solution of Recursive Program schemes, Theoret. Comput. Sci. 366 (2006) 3–59]. The main results are correct, but we offer some changes to the definitions and proofs concerning interpreted Recursive Program schemes
-
the category theoretic solution of Recursive Program schemes
arXiv: Logic in Computer Science, 2009Co-Authors: Stefan Milius, Lawrence S MossAbstract:This paper provides a general account of the notion of Recursive Program schemes, studying both uninterpreted and interpreted solutions. It can be regarded as the category-theoretic version of the classical area of algebraic semantics. The overall assumptions needed are small indeed: working only in categories with "enough final coalgebras" we show how to formulate, solve, and study Recursive Program schemes. Our general theory is algebraic and so avoids using ordered, or metric structures. Our work generalizes the previous approaches which do use this extra structure by isolating the key concepts needed to study substitution in infinite trees, including second-order substitution. As special cases of our interpreted solutions we obtain the usual denotational semantics using complete partial orders, and the one using complete metric spaces. Our theory also encompasses implicitly defined objects which are not usually taken to be related to Recursive Program schemes. For example, the classical Cantor two-thirds set falls out as an interpreted solution (in our sense) of a Recursive Program scheme.
-
equational properties of Recursive Program scheme solutions
Cahiers de Topologie et Géométrie Différentielle Catégoriques, 2009Co-Authors: Stefan Milius, Lawrence S MossAbstract:Dans leurs precedents travaux [17, 18, 19], les auteurs ont propose une theorie generale des schemas de Programmes recursifs et de leurs solutions. Ces travaux generalisaient des approches plus anciennes, qui utilisaient les ensembles ordonnes ou les espaces metriques en offrant une theorie utilisant le concept de coalgebre finale, d'algebre d'Elgot, et une grande partie de ce que l'on sait a leur sujet. La theorie donnait l'existence et l'unicite des solutions de schemas de Programmes recursifs non interpretes tres generaux. En outre, nous donnions aussi une theorie des solutions interpretees. Cet article poursuit le developpement de la theorie. Il fournit des principes generaux qui sont utilises pour montrer que deux schemas de Programmes recursifs dans notre sens ont les solutions non interpretees identiques ou liees, ou qu'ils ont des solutions correctement lies a l'interpretation, identiques ou liees.
-
corrigendum corrigendum to the category theoretic solution of Recursive Program schemes theoret comput sci 366 2006 3 59
Theoretical Computer Science, 2008Co-Authors: Stefan Milius, Lawrence S MossAbstract:This is a corrigendum for our paper [S. Milius, L.S. Moss, The category theoretic solution of Recursive Program schemes, Theoret. Comput. Sci. 366 (2006) 3-59]. The main results are correct, but we offer some changes to the definitions and proofs concerning interpreted Recursive Program schemes.
-
Corrigendum: Corrigendum to: “The category theoretic solution of Recursive Program schemes” [Theoret. Comput. Sci. 366 (2006) 3-59]
Theoretical Computer Science, 2008Co-Authors: Stefan Milius, Lawrence S MossAbstract:This is a corrigendum for our paper [S. Milius, L.S. Moss, The category theoretic solution of Recursive Program schemes, Theoret. Comput. Sci. 366 (2006) 3-59]. The main results are correct, but we offer some changes to the definitions and proofs concerning interpreted Recursive Program schemes.
Fritz Wysotzki - One of the best experts on this subject based on the ideXlab platform.
-
Programming by analogy retrieval mapping adaptation and generalization of Recursive Program schemes
2007Co-Authors: Ute Schmid, Fritz WysotzkiAbstract:We present an approach to Program reuse by analogical transfer based upon the notion of Recursive Program schemes (RPSs). RPSs are representations which capture the structure of a Program and are executable (if the symbols are interpreted by operator symbols of a functional Programming language). This kind of representation is extremly useful for Programming by analogy. The general outline of our approach is as follows: we start with a straight-forward Program (initial Program) which can be seen as handsimulation for transforming a fixed input into the corresponding output value. The desired iterative (Recursive) Program generalizing over the fixed input (RPS) is constructed by analogical transfer of an already known RPS which is structural similar to the new Programming problem. Source and target RPSs are generalized to an RPS representing the common structure of both problems. Target RPS and generalized RPS are stored in memory with the generalized RPS as parent to source and target. By building a hierachical memory of generalized RPSs we can use Programs as well as abstract schemes as sources. In this paper we present our approach to retrieval from and stepwise construction of an hierarchical memory and an algorithm and first results for adaptation of isomorphical and non-isomorphical sources.
-
Folding of finite Program terms to Recursive Program schemes
Proceedings First International IEEE Symposium Intelligent Systems, 2002Co-Authors: E. Kitzelmann, Ute Schmid, M. Muhlpfordt, Fritz WysotzkiAbstract:We present an approach to inductive synthesis of functional Programs based on the detection of recurrence relations. A given term is considered as the kth unfolding of an unknown Recursive Program. If a recurrence relations can be identified in the term, it can be folded into a Recursive Program which: (a) can reproduce the term and (b) generalizes over it. Our approach goes beyond Summers' classical approach (1977) in several aspects: it is language independent and works for terms belonging to an arbitrary term algebra; it allows induction of sets of Recursive equations which are in some arbitrary 'calls' relation; induced equations can be dependent on more than one input parameters and we can detect interdependencies of variable substitutions in Recursive calls; the given input terms can represent incomplete unfoldings of an hypothetical Recursive Program.
-
ECML - Induction of Recursive Program Schemes
Machine Learning: ECML-98, 1998Co-Authors: Ute Schmid, Fritz WysotzkiAbstract:In this paper we present an approach to the induction of Recursive structures from examples which is based on the notion of Recursive Program schemes. We separate induction from examples in two stages: (1) constructing initial Programs from examples and (2) folding initial Programs to Recursive Program schemes. By this separation, the induction of Recursive Program schemes can be reduced to a pattern-matching problem which can be handled by a generic algorithm. Construction of initial Programs is performed with an approach to universal planning. "Background knowledge" is given in the form of operators and their conditions of application. Furthermore synthesizing Recursive Program schemes instead of Programs in a predefined Programming language enables us to combine Program synthesis and analogical reasoning. A Recursive Program scheme represents the class of structural identical Programs and can be assigned different semantics by interpretation. We believe that our approach mimicks in some way the problem solving and learning behavior of a (novice) human Programmer and that our approach integrates theoretical ideas and empirical results of learning by doing and learning by analogy from cognitive science in a unique framework.
-
induction of Recursive Program schemes
European conference on Machine Learning, 1998Co-Authors: Ute Schmid, Fritz WysotzkiAbstract:In this paper we present an approach to the induction of Recursive structures from examples which is based on the notion of Recursive Program schemes. We separate induction from examples in two stages: (1) constructing initial Programs from examples and (2) folding initial Programs to Recursive Program schemes. By this separation, the induction of Recursive Program schemes can be reduced to a pattern-matching problem which can be handled by a generic algorithm. Construction of initial Programs is performed with an approach to universal planning. "Background knowledge" is given in the form of operators and their conditions of application. Furthermore synthesizing Recursive Program schemes instead of Programs in a predefined Programming language enables us to combine Program synthesis and analogical reasoning. A Recursive Program scheme represents the class of structural identical Programs and can be assigned different semantics by interpretation. We believe that our approach mimicks in some way the problem solving and learning behavior of a (novice) human Programmer and that our approach integrates theoretical ideas and empirical results of learning by doing and learning by analogy from cognitive science in a unique framework.
Stefan Milius - One of the best experts on this subject based on the ideXlab platform.
-
Corrigendum to: “The category theoretic solution of Recursive Program schemes” [Theoret. Comput. Sci. 366 (2006) 3–59]
Theoretical Computer Science, 2020Co-Authors: Stefan Milius, Lawrence S MossAbstract:AbstractThis is a corrigendum for our paper [S. Milius, L.S. Moss, The category theoretic solution of Recursive Program schemes, Theoret. Comput. Sci. 366 (2006) 3–59]. The main results are correct, but we offer some changes to the definitions and proofs concerning interpreted Recursive Program schemes
-
Recursive Program schemes and context free monads
Electronic Notes in Theoretical Computer Science, 2010Co-Authors: Jiři Adamek, Stefan Milius, Jiři VelebilAbstract:Solutions of Recursive Program schemes over a given signature @S were characterized by Bruno Courcelle as precisely the context-free (or algebraic) @S-trees. These are the finite and infinite @S-trees yielding, via labelling of paths, context-free languages. Our aim is to generalize this to finitary endofunctors H of general categories: we construct a monad C^H ''generated'' by solutions of Recursive Program schemes of type H, and prove that this monad is ideal. In case of polynomial endofunctors of Set our construction precisely yields the monad of context-free @S-trees of Courcelle. Our result builds on a result by N. Ghani et al on solutions of algebraic systems.
-
CMCS - Recursive Program Schemes and Context-Free Monads
Electronic Notes in Theoretical Computer Science, 2010Co-Authors: Jiři Adamek, Stefan Milius, Jiři VelebilAbstract:Solutions of Recursive Program schemes over a given signature @S were characterized by Bruno Courcelle as precisely the context-free (or algebraic) @S-trees. These are the finite and infinite @S-trees yielding, via labelling of paths, context-free languages. Our aim is to generalize this to finitary endofunctors H of general categories: we construct a monad C^H ''generated'' by solutions of Recursive Program schemes of type H, and prove that this monad is ideal. In case of polynomial endofunctors of Set our construction precisely yields the monad of context-free @S-trees of Courcelle. Our result builds on a result by N. Ghani et al on solutions of algebraic systems.
-
the category theoretic solution of Recursive Program schemes
arXiv: Logic in Computer Science, 2009Co-Authors: Stefan Milius, Lawrence S MossAbstract:This paper provides a general account of the notion of Recursive Program schemes, studying both uninterpreted and interpreted solutions. It can be regarded as the category-theoretic version of the classical area of algebraic semantics. The overall assumptions needed are small indeed: working only in categories with "enough final coalgebras" we show how to formulate, solve, and study Recursive Program schemes. Our general theory is algebraic and so avoids using ordered, or metric structures. Our work generalizes the previous approaches which do use this extra structure by isolating the key concepts needed to study substitution in infinite trees, including second-order substitution. As special cases of our interpreted solutions we obtain the usual denotational semantics using complete partial orders, and the one using complete metric spaces. Our theory also encompasses implicitly defined objects which are not usually taken to be related to Recursive Program schemes. For example, the classical Cantor two-thirds set falls out as an interpreted solution (in our sense) of a Recursive Program scheme.
-
equational properties of Recursive Program scheme solutions
Cahiers de Topologie et Géométrie Différentielle Catégoriques, 2009Co-Authors: Stefan Milius, Lawrence S MossAbstract:Dans leurs precedents travaux [17, 18, 19], les auteurs ont propose une theorie generale des schemas de Programmes recursifs et de leurs solutions. Ces travaux generalisaient des approches plus anciennes, qui utilisaient les ensembles ordonnes ou les espaces metriques en offrant une theorie utilisant le concept de coalgebre finale, d'algebre d'Elgot, et une grande partie de ce que l'on sait a leur sujet. La theorie donnait l'existence et l'unicite des solutions de schemas de Programmes recursifs non interpretes tres generaux. En outre, nous donnions aussi une theorie des solutions interpretees. Cet article poursuit le developpement de la theorie. Il fournit des principes generaux qui sont utilises pour montrer que deux schemas de Programmes recursifs dans notre sens ont les solutions non interpretees identiques ou liees, ou qu'ils ont des solutions correctement lies a l'interpretation, identiques ou liees.
Ute Schmid - One of the best experts on this subject based on the ideXlab platform.
-
data driven detection of Recursive Program schemes
European Conference on Artificial Intelligence, 2010Co-Authors: Martin Hofmann, Ute SchmidAbstract:We present an extension to a current approach to inductive Programming (IGOR2), that is, learning (Recursive) Programs from incomplete specifications such as input/outout examples. IGOR2 uses an analytical, example-driven strategy for generalization. We extend the set of IGOR2's refinement operators by a further operator --identification of higher-order schemes --and can show that this extension does improve speed as well as scope.
-
ECAI - Data-Driven Detection of Recursive Program Schemes
2010Co-Authors: Martin Hofmann, Ute SchmidAbstract:We present an extension to a current approach to inductive Programming (IGOR2), that is, learning (Recursive) Programs from incomplete specifications such as input/outout examples. IGOR2 uses an analytical, example-driven strategy for generalization. We extend the set of IGOR2's refinement operators by a further operator --identification of higher-order schemes --and can show that this extension does improve speed as well as scope.
-
Programming by analogy retrieval mapping adaptation and generalization of Recursive Program schemes
2007Co-Authors: Ute Schmid, Fritz WysotzkiAbstract:We present an approach to Program reuse by analogical transfer based upon the notion of Recursive Program schemes (RPSs). RPSs are representations which capture the structure of a Program and are executable (if the symbols are interpreted by operator symbols of a functional Programming language). This kind of representation is extremly useful for Programming by analogy. The general outline of our approach is as follows: we start with a straight-forward Program (initial Program) which can be seen as handsimulation for transforming a fixed input into the corresponding output value. The desired iterative (Recursive) Program generalizing over the fixed input (RPS) is constructed by analogical transfer of an already known RPS which is structural similar to the new Programming problem. Source and target RPSs are generalized to an RPS representing the common structure of both problems. Target RPS and generalized RPS are stored in memory with the generalized RPS as parent to source and target. By building a hierachical memory of generalized RPSs we can use Programs as well as abstract schemes as sources. In this paper we present our approach to retrieval from and stepwise construction of an hierarchical memory and an algorithm and first results for adaptation of isomorphical and non-isomorphical sources.
-
Folding of finite Program terms to Recursive Program schemes
Proceedings First International IEEE Symposium Intelligent Systems, 2002Co-Authors: E. Kitzelmann, Ute Schmid, M. Muhlpfordt, Fritz WysotzkiAbstract:We present an approach to inductive synthesis of functional Programs based on the detection of recurrence relations. A given term is considered as the kth unfolding of an unknown Recursive Program. If a recurrence relations can be identified in the term, it can be folded into a Recursive Program which: (a) can reproduce the term and (b) generalizes over it. Our approach goes beyond Summers' classical approach (1977) in several aspects: it is language independent and works for terms belonging to an arbitrary term algebra; it allows induction of sets of Recursive equations which are in some arbitrary 'calls' relation; induced equations can be dependent on more than one input parameters and we can detect interdependencies of variable substitutions in Recursive calls; the given input terms can represent incomplete unfoldings of an hypothetical Recursive Program.
-
ECML - Induction of Recursive Program Schemes
Machine Learning: ECML-98, 1998Co-Authors: Ute Schmid, Fritz WysotzkiAbstract:In this paper we present an approach to the induction of Recursive structures from examples which is based on the notion of Recursive Program schemes. We separate induction from examples in two stages: (1) constructing initial Programs from examples and (2) folding initial Programs to Recursive Program schemes. By this separation, the induction of Recursive Program schemes can be reduced to a pattern-matching problem which can be handled by a generic algorithm. Construction of initial Programs is performed with an approach to universal planning. "Background knowledge" is given in the form of operators and their conditions of application. Furthermore synthesizing Recursive Program schemes instead of Programs in a predefined Programming language enables us to combine Program synthesis and analogical reasoning. A Recursive Program scheme represents the class of structural identical Programs and can be assigned different semantics by interpretation. We believe that our approach mimicks in some way the problem solving and learning behavior of a (novice) human Programmer and that our approach integrates theoretical ideas and empirical results of learning by doing and learning by analogy from cognitive science in a unique framework.
Tim Fernando - One of the best experts on this subject based on the ideXlab platform.
-
ICALP - Provably Recursive Programs and Program Extraction
Automata Languages and Programming, 1991Co-Authors: Tim FernandoAbstract:There is, clearly, more to a Program than the function it computes. Nevertheless, the relationship between notions of computation and deduction is commonly made precise over a formal theory by isolating that theory's class of provably Recursive functions — i.e., the Recursive functions the theory proves total. Replacing the “function” in “provably Recursive function” by “Program”, the present paper investigates the notion of a provably Recursive Program, uncovering certain holes and complexities that the concept of a provably Recursive function abstracts away.
-
provably Recursive Programs and Program extraction
International Colloquium on Automata Languages and Programming, 1991Co-Authors: Tim FernandoAbstract:There is, clearly, more to a Program than the function it computes. Nevertheless, the relationship between notions of computation and deduction is commonly made precise over a formal theory by isolating that theory's class of provably Recursive functions — i.e., the Recursive functions the theory proves total. Replacing the “function” in “provably Recursive function” by “Program”, the present paper investigates the notion of a provably Recursive Program, uncovering certain holes and complexities that the concept of a provably Recursive function abstracts away.