Binary trees as a computational framework

We present a new set of algorithms for performing arithmetic computations on the set of natural numbers, represented as ordered rooted binary trees. We show formally that these algorithms are correct and discuss their time and space complexity in comparison to traditional arithmetic operations on bitstrings.Our binary tree algorithms follow the structure of a simple type language, similar to that of Gödel's System T.Generic implementations using Haskell's type class mechanism are shared between instances shown to be isomorphic to the set of natural numbers. This representation independence is illustrated by instantiating our computational framework to the language of balanced parenthesis languages.The self-contained source code of the paper is available at http://logic.cse.unt.edu/tarau/research/2012/jtypes.hs.     

A Note on Complexity Measures for Inductive Classes in Constructive Type Theory

It is notoriously hard to express computational complexity properties of programs in programming logics based on a semantics which respects extensional function equality. That is a serious impediment to applications of programming logics requiring reasoning about complexity. This paper shows how to use existing mechanisms to define internal computational complexity measures in logics that support inductively defined types, dependent products, and functions. The method exploits a feature of inductive definitions in constructive type theory, namely that implicit proof codes are kept with the objects showing how they are presented in the inductive class. The idea is illustrated by giving a formal inductive definition ofPTimebased on ideas from Leivant's work and on Bellantoni and Cook's approach. Then a complexity measure is defined on elements of this class. This paper discusses the limitations of this idea and the need forfaithfulnessguarantees that link internal complexity classes to the implementation of the logic. The paper concludes with a definition ofresource bounded logicsand a discussion of interesting lines of investigation of these logics which have the potential to make practical uses of results from computational complexity theory in formal reasoning about the efficiency of programs.     

Polynomial certificates for propositional classes

This paper studies the complexity of learning classes of expressions in propositional logic from equivalence queries and membership queries. In particular, we focus on bounding the number of queries that are required to learn the class ignoring computational complexity. This quantity is known to be captured by a combinatorial measure of concept classes known as the certificate complexity. The paper gives new constructions of polynomial size certificates for monotone expressions in conjunctive normal form (CNF), for unate CNF functions where each variable affects the function either positively or negatively but not both ways, and for Horn CNF functions. Lower bounds on certificate size for these classes are derived showing that for some parameter settings the new certificate constructions are optimal. Finally, the paper gives an exponential lower bound on the certificate size for a natural generalization of these classes known as renamable Horn CNF functions, thus implying that the class is not learnable from a polynomial number of queries.     

Logic programs as compact denotations

This paper shows how logic programs can be used to implement the transition functions of denotational abstract interpretation. The logic variables express regularity in the abstract behaviour of commands. The technique has been applied to sign, class and escape analysis for object-oriented programs. We show that the time and space costs using logic programs for these analyses are smaller than those using a ground relational representation. Moreover, we show that, in the case of sign analysis, our technique requires less memory and has an efficiency comparable to that of an implementation based on binary decision diagrams.     

A continuum of discrete systems

We show how to regard covered logic programs as cellular automata. Covered logic programs are ones for which every variable occurring in the body of a given clause also occurs in the head of the same clause. We generalize the class of register machine programs to permit negative literals and characterize the members of this class of programs as n-state 2-dimensional cellular automata. We show how monadic covered programs, the class of which is computationally universal, can be regarded as 1-dimensional cellular automata. We show how to continuously (and differentiably) deform 1-dimensional cellular automata from one to another and understand the arrangement of these cellular automata in a separable Hilbert space over the real numbers. The embedding of the cellular automata of fixed radius r is a linear mapping into R^{2 2r+1} in which a cellular automaton's transition function is the attractor of a state-governed iterated function system of affine contraction mappings. The class of covered monadic programs having a particular fixed point has a uniform arrangement in an affine subspace of the Hilbert space l². Furthermore, these programs are construable as almost everywhere continuous functions from the unit interval {x | 0 ≤ x ≤ 1} to the real numbers R. As one consequence, in particular, we can define a variety of natural metrics on the class of these programs. Moreover, for each program in this class, the set of initial segments of the program's fixed points, with respect to an ordering induced by the program's dependency relation, is a regular set. This revised version was published online in June 2006 with corrections to the Cover Date.     

Complexity dichotomy on partial grid recognition

Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a number of graph classes for which the problem is polynomial, even trivial. A natural step, outstanding thus far, was to provide a broad classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of allowed vertex degrees in the input graphs, yielding a full dichotomy on the complexity of the problem. As byproducts, the previous NP-completeness result for binary trees was strengthened to strictly binary trees, and the three-dimensional version of the problem was for the first time proven to be NP-complete. Our results were made possible by introducing the concepts of consistent orientations and robust gadgets, and by showing how the former allows NP-completeness proofs by local replacement even in the absence of the latter.     

Regular Languages of Thin Trees

An infinite tree is called thin if it contains only countably many infinite branches. Thin trees can be seen as intermediate structures between infinite words and infinite trees. In this work we investigate properties of regular languages of thin trees. Our main tool is an algebra suitable for thin trees. Using this framework we characterize various classes of regular languages: commutative, open in the standard topology, and definable in weak MSO logic among all trees. We also show that in various meanings thin trees are not as rich as all infinite trees. In particular we observe a collapse of the parity index to the level (1, 3) and a collapse of the topological complexity to co-analytic sets. Moreover, a gap property is shown: a regular language of thin trees is either weak MSO-definable among all trees or co-analytic-complete.     

The completeness of functional logic

A new first-order logic, functional logic, was proposed recently by Staples, Robinson and Hazel. The logic provides a formal means of describing and reasoning about dependence on an implicit parameter, a prime motivation being the unification of the Hoare logic used to reason about procedural programs with the powerful and well established techniques of classical logic. Viewed more abstractly, independently of possible applications, functional logic may be described as a logic with primitives, axioms and inference rules appropriate for reasoning about the properties of mathematical functions. In this paper, the completeness of functional logic is proved; that is, it is shown that any term of a theory in the logic which is true in all models is a theorem.This work was done while the author was a visitor to the Key Centre for Software Technology, Department of Computer Science, The University of Queensland, Queensland 4072, Australia.     

Experimental comparison of decomposition methods for systems of Boolean function

In this paper, we describe the results of the experimental comparison of programs that implement various decomposition methods for disjunctive normal forms of systems of completely defined Boolean functions. The complexity of a system of disjunctive normal forms is expressed in two ways: by the area of a programmable logic array that implements a system of disjunctive normal forms, or by the number of vertices of a binary decision diagram, which represents a system of Boolean functions. The complexity of the functional expansion of a system’s functions is determined as the sum of the complexities of the subsystem of the functions included in this expansion. The estimates of the complexity are oriented on the synthesis of combinational circuits based on the programmed logical arrays and the library’s logical elements.     

A new implementation technique for applicative languages

It is shown how by using results from combinatory logic an applicative language, such as LISP, can be translated into a form from which all bound variables have been removed. A machine is described which can efficiently execute the resulting code. This implementation is compared with a conventional interpreter and found to have a number of advantages. Of these the most important is that programs which exploit higher order functions to achieve great compactness of expression are executed much more efficiently.     

Logic programming with infinite sets

Using the ideas from current investigations in Knowledge Representation we study the use of a class of logic programs for reasoning about infinite sets. Our programs reason about the codes for various infinite sets. Depending on the form of atoms allowed in the bodies of clauses we obtain a variety of completeness results for various classes of arithmetic sets of integers.AMS subject classification 68T27, 03B70     

Stable and extension class theory for logic programs and default logics

The stable model semantics (cf. Gelfond and Lifschitz [1]) for logic programs suffers from the problem that programs may not always have stable models. Likewise, default theories suffer from the problem that they do not always have extensions. In such cases, both these formalisms for non-monotonic reasoning have an inadequate semantics. In this paper, we propose a novel idea-that of extension classes for default logics, and of stable classes for logic programs. It is shown that the extension class and stable class semantics extend the extension and stable model semantics respectively. This allows us to reason about inconsistent default theories, and about logic programs with inconsistent completions. Our work extends the results of Marek and Truszczynski [2] relating logic programming and default logics.     

Automatic program debugging for intelligent tutoring systems

Program debugging is an important part of the domain expertise required for intelligent tutoring systems that teach programming languages. This article explores the process by which student programs can be automatically debugged in order to increase the instructional capabilities of these systems. The research presented provides a methodology and implementation for the diagnosis and correction of nontrivial recursive programs. In this approach, recursive programs are debugged by repairing induction proofs in the Boyer-Moore logic. The induction proofs constructed and debugged assert the computational équivalence of student programs to correct exemplar solutions. Exemplar solutions not only specify correct implementations but also provide correct code to replace buggy student code. Bugs in student code are repaired with heuristics that attempt to minimize the scope of repair. The automated debugging of student code is greatly complicated by the tremendous variability that arises in student solutions to nontrivial tasks. This variability can be coped with, and debugging performance improved, by explicit reasoning about computational semantics during the debugging process. This article supports these claims by discussing the design, implementation, and evaluation of Talus, an automatic debugger for LISP programs, and by examining related work in automated program debugging. Talus relies on its abilities to reason about computational semantics to perform algorithm recognition, infer code teleology, and to automatically detect and correct nonsyntactic errors in student programs written in a restricted, but nontrivial, subset of LISP. Solutions can vary significantly in algorithm, functional decomposition, role of variables, data flow, control flow, values returned by functions, LISP primitives used, and identifiers used. Solutions can consist of multiple functions, each containing multiple bugs. Empiricial evaluation demonstrates that Talus achieves high performance in debugging widely varying student solutions to challenging tasks.     

Inductive inference of logic programs based on algebraic semantics

In this paper we present a new inductive inference algorithm for a class of logic programs, calledlinear monadic logic programs. It has several unique features not found in Shapiro’s Model Inference System. It has been proved that a set of trees isrational if and only if it is computed by a linear monadic logic program, and that the rational set of trees is recognized by a tree automaton. Based on these facts, we can reduce the problem of inductive inference of linear monadic logic programs to the problem of inductive inference of tree automata. Further several efficient inference algorithms for finite automata have been developed. We extend them to an inference algorithm for tree automata and use it to get an efficient inductive inference algorithm for linear monadic logic programs. The correctness, time complexity and several comparisons of our algorithm with Model Inference System are shown.     

Complexity of computing with extended propositional logic programs

In this paper we introduce the notion of anF-program, whereF is a collection of formulas. We then study the complexity of computing withF-programs.F-programs can be regarded as a generalization of standard logic programs. Clauses (or rules) ofF-programs are built of formulas fromF. In particular, formulas other than atoms are allowed as building blocks ofF-program rules. Typical examples ofF are the set of all atoms (in which case the class of ordinary logic programs is obtained), the set of all literals (in this case, we get the class of logic programs with classical negation [9]), the set of all Horn clauses, the set of all clauses, the set of all clauses with at most two literals, the set of all clauses with at least three literals, etc. The notions of minimal and stable models [16, 1, 7] of a logic program have natural generalizations to the case ofF-programs. The resulting notions are called in this paperminimal andstable answer sets. We study the complexity of reasoning involving these notions. In particular, we establish the complexity of determining the existence of a stable answer set, and the complexity of determining the membership of a formula in some (or all) stable answer sets. We study the complexity of the existence of minimal answer sets, and that of determining the membership of a formula in all minimal answer sets. We also list several open problems.This work was partially supported by National Science Foundation under grant IRI-9012902.This work was partially supported by National Science Foundation under grant CCR-9110721.     

基于Visual LISP的分形自相似图形造型算法与实现

分形几何学是目前研究的一个热点,其中的自相似图形可以模拟自然界中的一些现象。该文提出了利用AutoCAD)强大的绘图功能,根据它的独有的、“先画先存”的、表存储结构的图形数据库的特点,在Visual LISP开发环境中,用LISP函数实现典型分形几何中典型自相似图形的造型算法,同时设计出与它对应的自定义菜单,实现在AutoCAD中对分形几何自相似图形的仿真。可以将这种方法应用于教学、科研中的几何分析与图形演示等场合。     

Efficient majority logic magnitude comparator design

Majority, minority gates and inverters are the natural logic element of several beyond-CMOS emerging nanotechnologies. Magnitude comparators are components used in computer systems to compare if two binary numbers are equal or if one number is greater or less than the other. Therefore, efficient majority logic implementation of magnitude comparators is highly desirable. The proposed majority logic magnitude comparators have lower circuit and delay complexity compared against the already published majority logic magnitude comparator designs.