Inductive inference of regular languages based on model inference

This paper is concerned with an algorithm for identifying an unknown regular language from examples of its members and non-members. The algorithm is based on the model inference algorithm given by Shapiro. In our setting, however, a given first order language for describing a target logic program has countably many unary predicate symbols: q ₀,q ₁,q ₂…. On the other hand, the oracle which gives information about the unknown regular language to the inference algorithm has no interpretation for predicates other than the predicate q ₀. In such a setting,we cannot directly take advantage of the contradiction backtracing algorithm which is one of the most important parts for the efficiency of the model inference algorithm. In order to overcome this disadvantage, we develop a method for giving an interpretation for predicates other than the predicate q ₀ indirectly, which is based on the idea of using the oracle and a one to one mapping from a set of predicates to a set of strings. Furthermore, we propose a model inference algorithm for regular languages using the method, then argue the correctness and the time complexity of the algorithm     

Inductive inference and software testing

The term ‘inductive inference’ denotes the process of hypothesizing a general rule from examples. It can be considered as the inverse process of program testing, which is a process of sampling the behaviour of a program and gathering confidence in the quality of the software from the samples. As one of the fundamental and ubiquitous components of intelligent behaviour, much effort has been spent on both the theory and practice of inductive inference as a branch of artificial intelligence. In this paper, software testing and inductive inference are reviewed to illustrate how the rich and solid theory of inductive inference can be used to study the foundations of software testing.     

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.     

直觉F推理与普通F推理的比较研究

直觉F推理克服了普通F推理在不确定性信息的描述、推理结果可信性等方面存在的局限性。在介绍普通F推理直觉化扩展的基础上,首先分析了两类推理算法的相互转化问题,指出普通F推理是直觉F推理的一种特例,当直觉指数为0时二者可相互转化。其次,比较了两类算法的还原性,分析表明Zadeh型、Mamdani型、Larsen型直觉F推理算法与其对应的普通F推理算法具有相同的还原性。最后,通过实例研究了直觉F推理算法在推理结果精度、可信性上的优势,从而较普通F推理更适用于智能控制与决策。     

On some open problems in reflective inductive inference

In this paper we show that there exist classes of functions which can be learnt by a finite learner which reflects on its capability, but not learnable by a consistent learner which optimistically reflects on its capability. This solves the two mentioned open problems from [G. Grieser, Reflective inductive inference of recursive functions, Theoretical Computer Science A 397 (1-3) (2008) 57-69 (Special Issue on Forty Years of Inductive Inference. Dedicated to the 60th Birthday of Rolf Wiehagen)].     

归纳逻辑程序设计综述

归纳逻辑程序设计是由机器学习与逻辑程序设计交叉所形成的一个研究领域,是机器学习的前沿研究课题。该文首先从归纳逻辑程序设计的问题背景、类型划分和搜索程序子句三个方面介绍了归纳逻辑程序设计系统的概貌;然后结合实验室的相关研究工作,回顾了归纳逻辑程序设计研究的发展;之后介绍了归纳逻辑程序设计领域中需要深入研究的若干问题,并提出了新的解决思路;最后是总结,以引起读者对归纳逻辑程序设计领域研究的进一步关注。     

约束归纳逻辑程序设计方法的研究

提出了一种新的约束归纳逻辑程序设计方法。该方法能够与自顶向下的归纳逻辑程序设计系统结合,通过在自顶向下归纳方法的一步特殊化操作中引入Fisher判别分析等方法,使得系统能够导出不受变量个数限制的多种形式的线性约束,在不需要用户诱导,不依赖约束求解器的情况下,学习出覆盖正例而排斥负例的含约束的Horn子句程序。     

Inductive families

A general formulation of inductive and recursive definitions in Martin-Löf's type theory is presented. It extends Backhouse's Do-It-Yourself Type Theory to include inductive definitions of families of sets and definitions of functions by recursion on the way elements of such sets are generated. The formulation is in natural deduction and is intended to be a natural generalisation to type theory of Martin-Löf's theory of iterated inductive definitions in predicate logic.Formal criteria are given for correct formation and introduction rules of a new set former capturing definition by strictly positive, iterated, generalised induction. Moreover, there is an inversion principle for deriving elimination and equality rules from the formation and introduction rules. Finally, there is an alternative schematic presentation of definition by recursion.The resulting theory is a flexible and powerful language for programming and constructive mathematics. We hint at the wealth of possible applications by showing several basic examples: predicate logic, generalised induction, and a formalisation of the untyped lambda calculus.A shorter preliminary version of this paper appeared under the title An inversion principle for Martin-Löf's type theory in the Proceedings of the Workshop on Programming Logic in Båstad, May 1989, Programming Methodology Group Report 54, Chalmers University of Technology and the University of Göteborg, pages 177–190.     

归纳定义与递归算法

归纳定义是定义某些概念时常用到的一种定义方法，但是，什么叫做“归纳定义”并没有严格的说法，本文从代数系统的观点出发，对归纳定义进行了严格的数学定义。递归算法是编程时经常使用的一种算法设计方法，其思想就是算法本身调用自己。本文对归纳定义与递归算法之间的联系进行了深入的讨论和研究，结论是：利用归纳定义所定义的概念一定可以利用递归算法进行判定；反之，由递归算法可以判定的概念一定能够进行归纳定义。     

Bounded Recursively Enumerable Sets and Degrees

A new reducibility between the recursive sets is defined,which is appropriate to be used in the study of th polynomial reducibility and the NP-problem.     

Inductive semimodules and the vector modules over them

The notion of an inductive semimodule over an ordered *-semiring is introduced and some related properties are investigated. Inductive semimodules are extensions of several important algebraic structures such as Kleene modules, Kleene algebras and inductive *-semirings. We prove that an inductive semimodule over an ordered *-semiring K is a Kleene module if and only if K is a Kleene algebra. Moreover, we establish that the vector module of an inductive semimodule over an ordered Conway semiring is again an inductive semimodule over the matrix semiring. Consequently, in an inductive semimodule over an ordered Conway semiring, least solutions to linear inequation systems can be denoted by linear expressions, avoiding the least fixed point operator. In addition, we also introduce a related notion called weak inductive semimodules, and propose several open problems on them.

Strong monotonic and set-driven inductive inference

Abstract. In an earlier paper, Kinber and Stephan posed an open problem about whether every class of languages, which can be identified strong monotonically, can also be identified by a set-driven machine. This question is solved in this paper. The answer to the question depends on whether the machines are required to be total or not! The solution of this result uncovers a finer gradation of the notion of setdrivenness.     

粗糙集与模糊系统集成的化学模式分类方法及其应用

模糊方法是一种有效的化学模式分类方法,但模糊规则的获取和相关参数的确定较为困难。对此,本文采用粗糙集方法,无需任何先验知识,约简系统,获取最简规则集,在此基础上构建结构合理．适用于分类的模糊-神经网络系统,并根据规则的统计性质和离散化结果初始化网络参数,采用LM方法训练网络;在橄榄油模式分类建模的应用中,该方法训练收敛速度快,所建模型预测性能良好,要优于现代统计方法和前馈神经网络。     

基于非接触电能传输电路的技术分析

给出了非接触感应式电能传输的基本原理，针对松耦合电路，分析了影响电能传输效率的主要因素，研究可行的拓扑补偿结构，提高传输的有效性和稳定性，设计提出了一个可行性方案并开发出一个用于基本验证的功能样机。     

归纳法推理中若干问题的探讨

归纳法推理是人工智能领域中富有挑战性的研究方向,它是一种难度较大但较有前途的自动定理证明方法。文章对近年来归纳法推理的主要研究成果进行了综述,并分析国内外的研究现状,讨论了归纳法推理研究中的推理效率、理论的不完备性、自动推理机制和构造实用的定理证明器等问题。     

Inductive proximity sensor with a flat coil and a new differential relaxation oscillator

A high-sensitivity flat-coil inductive proximity sensor microsystem has been realized and successfully tested. The flat coil, made with CMOS-compatible post processes, is connected to a versatile differential relaxation oscillator electronic interface. In this new and simple interface, the excitation, the signal extraction and amplification are assured by only one operational amplifier. Experimental results on the microsystem confirm that large output frequency variations occur when a metallic target approaches the sensor.     

入侵检测中的归纳学习方法

结合使用着色Petri网和EDL语言描述攻击模型,该文给出了使用归纳学习对攻击模型进行泛化和特化操作,泛化后的模型可以检测出与已知攻击实例类似的未知攻击行为,实现了攻击知识库进行自动更新和扩展的方法。攻击实例首先使用EDL语言表述为一个攻击实例模型,对实例模型进行泛化得到攻击实例的3层概念空间,进而转化为着色Petri网模型,利用着色Petri网的运行机制对攻击行为进行检测。实验结果表明该方法对于具有相似攻击行为的未知攻击的检测非常有效。