Recursive functions of context free languages (Ⅱ)——Validity of CFPRF and CFRF definitions

In this paper we proved that the function class CFRF and its proper subclass CFPRF are respectively the partial recursive functions and primitive recursive functions of context free languages (CFLs). Also we discussed the relation between them and recursive functions defined on other domains . It is indicated that the functions of natural numbers and/or symbol strings (words) are functions of CFLs. Several frequently used primitive recursive functions on words were given, including logical connectives, conditional expressions. Also the powerful operators (bounded maximization and minimization operators) for constructing primitive recursive functions were defined. Two important nontrivial algorithms, the characteristic function of arbitrary CFL and the parse function of CFL sentences were constructed. Based on them, the method for extending or restricting function domain was described.     

Recursive functions of context free languages (I)

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. This paper is based on the Technical Report ISCAS-LCS-2k-03 (SAQ Report No. 30): Recursive Functions Defined on Context Free Languages (I), August 2000, with minor revisions.     

Recursive functions of context free languages (Ⅰ)——The definitions of CFPRF and CFRF

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.     

Recursive functions of context free languages (I)--The definitions of CFPRF and CFRF

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.     

On primitive recursive wordfunctions

In order to compare primitive recursive functions and transductions defined by automata in a natural way independent of encodings, we generalize the Grzegorczyk hierarchy, the recursion number hierarchy and the loop hierarchy from arithmetical to wordfunctions. We observe several differences between the arithmetical and the non-arithmetical theory. By means of turingmachines and generalized sequential machines all inclusion problems for the function classes of these hierarchies are solved. Transductions and languages defined by automata are classified within these hierarchies. Moreover, we introduce and study primitive recursive transformations between different monoids.     

A characterization of computable analysis on unbounded domains using differential equations

The functions of computable analysis are defined by enhancing normal Turing machines to deal with real number inputs. We consider characterizations of these functions using function algebras, known as real recursive functions. Since there are numerous incompatible models of computation over the reals, it is interesting to find that the two very different models we consider can be set up to yield exactly the same functions. Bournez and Hainry used a function algebra to characterize computable analysis, restricted to the twice continuously differentiable functions with compact domains. In our earlier paper, we found a different (and apparently more natural) function algebra that also yields computable analysis, with the same restriction. In this paper we improve earlier work, finding three function algebras characterizing computable analysis, removing the restriction to twice continuously differentiable functions and allowing unbounded domains. One of these function algebras is built upon the widely studied real primitive recursive functions. Furthermore, the proof of this paper uses our previously developed method of approximation, whose applicability is further evidenced by this paper.     

Fusion of recursive programs with computational effects

Fusion laws permit to eliminate various of the intermediate data structures that are created in function compositions. The fusion laws associated with the traditional recursive operators on datatypes cannot, in general, be used to transform recursive programs with effects. Motivated by this fact, this paper addresses the definition of two recursive operators on datatypes that capture functional programs with effects. Effects are assumed to be modeled by monads. The main goal is thus the derivation of fusion laws for the new operators. One of the new operators is called monadic unfold. It captures programs (with effects) that generate a data structure in a standard way. The other operator is called monadic hylomorphism, and corresponds to programs formed by the composition of a monadic unfold followed by a function defined by structural induction on the data structure that the monadic unfold generates.     

Transforming powerlist-based divide-and-conquer programs for an improved execution model

Powerlists are data structures that can be successfully used for defining parallel programs based on divide-and-conquer paradigm. These parallel recursive data structures and their algebraic theories offer both a methodology to design parallel algorithms and parallel programming abstractions to ease the development of parallel applications. The paper presents a technique for speeding up the parallel recursive programs defined based on powerlists. The improvements are achieved by applying transformation rules that introduce tuple functions and prefix operators, for which a more efficient execution model is defined. Together with the execution model, a cost model is also defined in order to allow a proper evaluation. The treated examples emphasise the fact that the transformation leads to important improvements of the programs. The speeding up is achieved by reducing the number of recursive calls, and also by enable the fusion of splitting/combining operations on different data structures. In addition, enhancing the function that has to be computed to other useful functions using a tuple, could improved the cost reduction even more.

     

Self-Monitoring Machines and anωHierarchy of Loops

An ordinal hierarchy of recursive functions is developed based on the level to which a function requires a machine computing it to monitor and make decisions concerning itself. The major theorem states that the functions with self-monitoring level belowω^ωare precisely the class of loop functions (or primitive recursive functions).     

Towards a logic programming methodology based on higher-order predicates

This paper outlines a logic programming methodology which applies standardized logic program recursion forms afforded by a system of general purpose recursion schemes. The recursion schemes are conceived of as quasi higher-order predicates which accept predicate arguments, thereby representing parameterized program modules. This use of higher-order predicates is analogous to higher-order functionals in functional programming. However, these quasi higher-order predicates are handled by a metalogic programming technique within ordinary logic programming. Some of the proposed recursion operators are actualizations of mathematical induction principles (e.g. structural induction as generalization of primitive recursion). Others are heuristic schemes for commonly occurring recursive program forms. The intention is to handle all recursions in logic programs through the given repertoire of higher-order predicates. We carry out a pragmatic feasibility study of the proposed recursion operators with respect to the corpus of common textbook logic programs. This pragmatic investigation is accompanied with an analysis of the theoretical expressivity. The main theoretical results concerning computability are

1. Primitive recursive functions can be re-expressed in logic programming by predicates defined solely by non-recursive clauses augmented with afold recursion predicate akin to the fold operators in functional programming.
2. General recursive functions can be re-expressed likewise sincefold allows re-expression of alinrec recursion predicate facilitating linear, unbounded recursion.

     

Self-Monitoring Machines and anωHierarchy of Loops

An ordinal hierarchy of recursive functions is developed based on the level to which a function requires a machine computing it to monitor and make decisions concerning itself. The major theorem states that the functions with self-monitoring level belowω^ωare precisely the class of loop functions (or primitive recursive functions).     

Nonconstructive Computational Mathematics

We describe a nonconstructive extension to primitive recursive arithmetic, both abstractly and as implemented on the Boyer-Moore prover. Abstractly, this extension is obtained by adding the unbounded µ operator applied to primitive recursive functions; doing so, one can define the Ackermann function and prove the consistency of primitive recursive arithmetic. The implementation does not mention the µ operator explicitly but has the strength to define the µ operator through the built-in functions EVAL$ and V&C$.     

运算构造和检验系统FC的设计和实现

运算构造和检验系统FC(function constructor)是形式规约获取系统SAQ(specification acquisition)的一个子系统.在SAQ系统中,运算用于表示规约的语义.FC提供了对运算的交互式归纳定义方式和运算的施用,支持运算的联立递归定义.详细介绍FC的功能、结构和实现技术,并讨论了下一步的改进方向.     

基于关系数据库有效地处理XPath函数

函数是XQuery和XPath查询语言的重要组成部分,XQuery1.0和XPath2.0定义的函数库中包含16类函数。文章针对XPath的一个核心函数库,讨论了基于关系数据库中如何有效地处理XPath函数,并给出了有效地转换XPath函数到SQL查询的算法。实验结果表明,笔者提出的转换算法是通用、高效的。     

Partial Functions in ACL2

We describe a method for introducing “partial functions” into ACL2, that is, functions not defined everywhere. The function “definitions” are actually admitted via the encapsulation principle: the new function symbol is constrained to satisfy the appropriate equation. This is permitted only when a witness function can be exhibited, establishing that the constraint is satisfiable. Of particular interest is the observation that every tail recursive definition can be witnessed in ACL2. We describe a macro that allows the convenient introduction of arbitrary tail recursive functions, and we discuss how such functions can be used to prove theorems about state machine models without reasoning about “clocks” or counting the number of steps until termination. Our macro for introducing “partial functions” also permits a variety of other recursive schemes, and we briefly illustrate some of them. This revised version was published online in August 2006 with corrections to the Cover Date.     

Beyond Recursive Real Functions

All recursive real functions are continuous; in fact all theB-recursive real functions are continuous for any oracleB, simply because Turing machines computing them are finite objects. But simple discontinuous functions such as step functions have to be in some sense “easy” if they have recursive values and break points, although they are not computable by the usual definition. It seems unfair to label them noncomputable in the entire region just because of a few break points. In this paper, we investigate the properties of broader classes ofalmost everywhere recursive,weakly almost everywhere recursive, andrecursively approximablereal-valued functions, which capture these “easy” step functions and many other nonrecursive functions. Recursive versions of the classical Lusin and Egoroff Theorems are proved. We also characterize the property of the limit of a recursive sequence of functions and show that different notions of convergence (uniform, pointwise, or in measure) will result in different characterizations of the limiting function.     

A fuzzy ID3 induction for linguistic data sets

In real life, humans communicate by means of words. Computing with words enables flexibility via fuzzy logic to reach more informative results for the classification and decision‐making. Fuzzy logic handles the imprecise information. In our paper, we propose a novel fuzzy ID3 algorithm for the classification on linguistic data set, where data can be given as linguistic variables. Linguistic variables are defined by using triangular fuzzy numbers given as LR (left‐right) fuzzy numbers. And weighted averaging based on levels (WABL) method is used as the defuzzification method for each data. Then, fuzzy c‐means algorithm is performed to handle the membership degrees for each variable given in each data set used in an experimental study. At last, the fuzzy ID3 algorithm is applied. The rules are generated, and the reasoning is done by different T‐operators. Our study is encouraged by (using) statistical analysis. In conclusion, it is seen that our algorithm proposed for linguistic data is as good as the proposed approach for numeric data. Also, it is shown that the proposed linguistic approach by using different T‐operators on linguistic data gives better results than numerical approach on some data sets.     

Acceptable functional programming systems

Summary In this paper we present a self-contained treatment of the theory of computable functions using acceptable functional programming systems. We construct a particular acceptable functional programming system. Within the framework of this system we prove two main theorems to show that, when working with substitution operators, the fixed point function defined by the mechanism of the system and the fixed point function defined by the recursion theorem are both equal to the least fixed point. Furthermore we show that the programs defined by the mechanism of the system are easier and faster than the ones defined by the recursion theorem. We make some suggestions about how to implement the system using a suitable environment. We also formulate a natural question: what is the relationship between substitution operators and computable operators?     

有限自动机定义函数的线性本原圈积分解

本文讨论有限自动机显表出定义函数ｆ的线性本原圈积分解问题。在该圈积分解之下,函数ｆ被表成线性外函数因子ｆＬ与线性本原内涵数因子ｆＮ的圈积,这里函数ｆＬ定义了一个线性弱可逆有限自动机ＭｆＬ,而函数ｆＮ定义了一个非线性有限自动机ＭｆＮ且其不能再分解成一非平凡的线性外函数与一非线性内函数的圈积。本文证明了一函数ｆ的任两线性本原内因子互为对方的线性本原内因子,从而证明了函数ｆ的线性本原圈积分解的唯一性。本