The Experts below are selected from a list of 23943 Experts worldwide ranked by ideXlab platform
Gunter Grieser - One of the best experts on this subject based on the ideXlab platform.
-
reflective inductive inference of Recursive Functions
Theoretical Computer Science, 2008Co-Authors: Gunter GrieserAbstract:In this paper, we investigate reflective inductive inference of Recursive Functions. A reflective IIM is a learning machine that is additionally able to assess its own competence. First, we formalize reflective learning from arbitrary, and from canonical, example sequences. Here, we arrive at four different types of reflection: reflection in the limit, optimistic, pessimistic and exact reflection. Then, we compare the learning power of reflective IIMs with each other as well as with the one of standard IIMs for learning in the limit, for consistent learning of three different types, and for finite learning.
-
reflective inductive inference of Recursive Functions
Lecture Notes in Computer Science, 2002Co-Authors: Gunter GrieserAbstract:In this paper, we investigate reflective inductive inference of Recursive Functions. A reflective IIM is a learning machine that is additionally able to assess its own competence. First, we formalize reflective learning from arbitrary example sequences. Here, we arrive at four different types of reflection: reflection in the limit, optimistic, pessimistic and exact reflection. Then, for learning in the limit, for consistent learning of three different types and for finite learning, we compare the learning power of reflective IIMs with each other as well as with the one of standard IIMs. Finally, we compare reflective learning from arbitrary input sequences with reflective learning from canonical input sequences. In this context, an open question regarding total-consistent identification could be solved: it holds T-CONS a C T-CONS.
Richard Statman - One of the best experts on this subject based on the ideXlab platform.
-
on the word problem for combinators
Rewriting Techniques and Applications, 2000Co-Authors: Richard StatmanAbstract:In 1936 Alonzo Church observed that the “word problem” for combinators is undecidable. He used his student Kleene’s representation of partial Recursive Functions as lambda terms. This illustrates very well the point that “word problems” are good problems in the sense that a solution either way - decidable or undecidable - can give useful information. In particular, this undecidability proof shows us how to program arbitrary partial Recursive Functions as combinators.
-
On the word problem for combinators
Lecture Notes in Computer Science, 2000Co-Authors: Richard StatmanAbstract:In 1936 Alonzo Church observed that the word problem for combinators is undecidable. He used his student Kleene's representation of partial Recursive Functions as lambda terms. This illustrates very well the point that word problems are good problems in the sense that a solution either way - decidable or undecidable - can give useful information. In particular, this undecidability proof shows us how to program arbitrary partial Recursive Functions as combinators. I never thought that this result was the end of the story for combinators. In particular, it leaves open the possibility that the unsolvable problem can be approximated by solvable ones. It also says nothing about word problems for interesting fragments i.e., sets of combinators not combinatorially complete. Perhaps the most famous subproblem is the problem for S terms. Recently, Waldmann has made significant progress on this problem. Prior, we solved the word problem for the Lark, a relative of S. Similar solutions can be given for the Owl (S * ) and Turing's bird U. Familiar decidable fragments include linear combinators and various sorts of typed combinators. Here we would like to consider several fragments of much greater scope. We shall present several theorems and an open problem.
Yunmei Dong - One of the best experts on this subject based on the ideXlab platform.
-
facilitating formal specification acquisition by using Recursive Functions on context free languages
Knowledge Based Systems, 2006Co-Authors: Haiming Chen, Yunmei DongAbstract:Although formal specification techniques are very useful in software development, the acquisition of formal specifications is a difficult task. This paper presents the formal specification language LFC, which is designed to facilitate the acquisition and validation of formal specifications. LFC uses context-free languages for syntactic aspect and relies on a new kind of Recursive Functions, i.e. Recursive Functions on context-free languages, for semantic aspect of specifications. Construction and validation of LFC specifications are machine-aided. The basic ideas behind LFC, the main aspects of LFC, and the use of LFC and illustrative examples are described.
-
Recursive Functions of context free languages i the definitions of cfprf and cfrf
Science in China Series F: Information Sciences, 2002Co-Authors: Yunmei DongAbstract:It is intended to establish the Recursive function theory on context free languages (CFLs). In this paper, the function class CFRF and its proper subclass CFPRF were defined on CFLs; it is quite straightforward to use them for describing non-numerical algorithms. In fact, they are respectively the partial Recursive Functions and primitive Recursive Functions of context free languages. The structure induction method for proving CFPRF function properties was presented. A method for CFL sentence enumeration was given, the minimization operator was defined. Based on CFL sentence enumeration, the minimization operator evaluation method was given. Finally, the design and implementation principles of executable specification languages with the CFRF as theoretical basis were discussed.
Gomes, Victor Pereira - One of the best experts on this subject based on the ideXlab platform.
-
Funções recursivas primitivas: caracterização e alguns resultados para esta classe de funções
Universidade Federal da Paraíba, 2016Co-Authors: Gomes, Victor PereiraAbstract:A classe das funções recursivas primitivas não constitui uma versão formal para a classe das funções algorítmicas, estudamos esta classe especial de funções numéricas devido ao fato de que muitas das funções conhecidas como algorítmicas são recursivas primitivas. A abordagem acerca da classe das funções recursivas primitivas tem como objetivo explorar esta classe especial de funções e, a partir disto, apresentar soluções para os seguintes problemas: (1) dada a classe das derivações recursivas primitivas, há um algoritmo, ou seja, um procedimento mecânico, para reconhecer derivações recursivas primitivas? (2) Existe uma função universal para a classe das funções recursivas primitivas? Se sim, essa função é recursiva primitiva? (3) Toda função algorítmica é recursiva primitiva? Para apresentar soluções para estas questões, nos pautamos no método hipotético-dedutivo e argumentamos com base nos manuais de Davis (1982), Mendelson (2009), Dias e Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), entre outros. Apresentamos a teoria das máquinas de Turing, que constitui uma versão formal para a noção intuitiva de algoritmo, e, em seguida, a famosa tese de Church-Turing, a qual identifica a classe das funções algorítmicas com a classe das funções Turing-computáveis. Exibimos a classe das funções recursivas primitivas, e mostramos que a mesma constitui uma subclasse das funções Turing-computáveis. Tendo explorado a classe das funções recursivas primitivas, como resultados, provamos que existe um algoritmo reconhecedor para a classe das derivações recursivas primitivas; que existe uma função universal para a classe das funções recursivas primitivas a qual não pertence a esta classe; e que nem toda função algorítmica é recursiva primitiva.The class of primitive Recursive Functions is not a formal version to the class of algorithmic Functions, we study this special class of numerical Functions due to the fact of that many of the Functions known as algorithmic are primitive Recursive. The approach on the class of primitive Recursive Functions aims to explore this special class of Functions and from that, present solutions for the following problems: (1) given the class of primitive Recursive derivations, is there an algorithm, that is, a mechanical procedure for recognizing primitive Recursive derivations? (2) Is there a universal function for the class of primitive Recursive Functions? If so, is this function primitive Recursive? (3) Are all the algorithmic Functions primitive Recursive? To provide solutions to these issues, we base on the hypothetical-deductive method and argue based on the works of Davis (1982), Mendelson (2009), Dias e Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), among others. We present the theory of Turing machines which is a formal version to the intuitive notion of algorithm, and after that the famous Church-Turing tesis which identifies the class of algorithmic Functions with the class of Turing-computable Functions. We display the class of primitive Recursive Functions and show that it is a subclass of Turing-computable Functions. Having explored the class of primitive Recursive Functions we proved as results that there is a recognizer algorithm to the class of primitive Recursive derivations; that there is a universal function to the class of primitive Recursive Functions which does not belong to this class; and that not every algorithmic function is primitive Recursive
-
Funções recursivas primitivas: caracterização e alguns resultados para esta classe de funções
'Portal de Periodicos UFPB', 2016Co-Authors: Gomes, Victor PereiraAbstract:The class of primitive Recursive Functions is not a formal version to the class of algorithmic Functions, we study this special class of numerical Functions due to the fact of that many of the Functions known as algorithmic are primitive Recursive. The approach on the class of primitive Recursive Functions aims to explore this special class of Functions and from that, present solutions for the following problems: (1) given the class of primitive Recursive derivations, is there an algorithm, that is, a mechanical procedure for recognizing primitive Recursive derivations? (2) Is there a universal function for the class of primitive Recursive Functions? If so, is this function primitive Recursive? (3) Are all the algorithmic Functions primitive Recursive? To provide solutions to these issues, we base on the hypothetical-deductive method and argue based on the works of Davis (1982), Mendelson (2009), Dias e Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), among others. We present the theory of Turing machines which is a formal version to the intuitive notion of algorithm, and after that the famous Church-Turing tesis which identifies the class of algorithmic Functions with the class of Turing-computable Functions. We display the class of primitive Recursive Functions and show that it is a subclass of Turing-computable Functions. Having explored the class of primitive Recursive Functions we proved as results that there is a recognizer algorithm to the class of primitive Recursive derivations; that there is a universal function to the class of primitive Recursive Functions which does not belong to this class; and that not every algorithmic function is primitive Recursive.Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESA classe das funções recursivas primitivas não constitui uma versão formal para a classe das funções algorítmicas, estudamos esta classe especial de funções numéricas devido ao fato de que muitas das funções conhecidas como algorítmicas são recursivas primitivas. A abordagem acerca da classe das funções recursivas primitivas tem como objetivo explorar esta classe especial de funções e, a partir disto, apresentar soluções para os seguintes problemas: (1) dada a classe das derivações recursivas primitivas, há um algoritmo, ou seja, um procedimento mecânico, para reconhecer derivações recursivas primitivas? (2) Existe uma função universal para a classe das funções recursivas primitivas? Se sim, essa função é recursiva primitiva? (3) Toda função algorítmica é recursiva primitiva? Para apresentar soluções para estas questões, nos pautamos no método hipotético-dedutivo e argumentamos com base nos manuais de Davis (1982), Mendelson (2009), Dias e Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), entre outros. Apresentamos a teoria das máquinas de Turing, que constitui uma versão formal para a noção intuitiva de algoritmo, e, em seguida, a famosa tese de Church-Turing, a qual identifica a classe das funções algorítmicas com a classe das funções Turing-computáveis. Exibimos a classe das funções recursivas primitivas, e mostramos que a mesma constitui uma subclasse das funções Turing-computáveis. Tendo explorado a classe das funções recursivas primitivas, como resultados, provamos que existe um algoritmo reconhecedor para a classe das derivações recursivas primitivas; que existe uma função universal para a classe das funções recursivas primitivas a qual não pertence a esta classe; e que nem toda função algorítmica é recursiva primitiva
Naohi Eguchi - One of the best experts on this subject based on the ideXlab platform.
-
Predicative Lexicographic Path Orders: An Application of Term Rewriting to the Region of Primitive Recursive Functions
arXiv: Logic, 2013Co-Authors: Naohi EguchiAbstract:In this paper we present a novel termination order the {\em predicative lexicographic path order} (PLPO for short), a syntactic restriction of the lexicographic path order. As well as lexicographic path orders, several non-trivial primitive Recursive equations, e.g., primitive recursion with parameter substitution, unnested multiple recursion, or simple nested recursion, can be oriented with PLPOs. It can be shown that the PLPO however only induces primitive Recursive upper bounds on derivation lengths of compatible rewrite systems. This yields an alternative proof of a classical fact that the class of primitive Recursive Functions is closed under those non-trivial primitive Recursive equations.
-
predicative lexicographic path orders an application of term rewriting to the region of primitive Recursive Functions
FOPARA, 2013Co-Authors: Naohi EguchiAbstract:In this paper we present a novel termination order the predicative lexicographic path order (PLPO for short), a syntactic restriction of the lexicographic path order. As well as lexicographic path orders, several non-trivial primitive Recursive equations, e.g., primitive recursion with parameter substitution, unnested multiple recursion, or simple nested recursion, can be oriented with PLPOs. It can be shown that the PLPO however only induces primitive Recursive upper bounds on derivation lengths of compatible rewrite systems. This yields an alternative proof of a classical fact that the class of primitive Recursive Functions is closed under those non-trivial primitive Recursive equations.
