文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Regular inference as a graph coloring problem
侵权投诉

Regular inference as a graph coloring problem

The paper addresses the issue of inferring all the solutions of a regular inference problem. More precisely,

Regular Inference as a graph coloring problem Francois Coste IRISA, Campus de Beaulieu 35042 RENNES Cedex FRANCE fcoste@irisa.fr, jnicolas@irisa.fr and

Jacques Nicolas

The paper addresses the issue of inferring all the solutions of a regular inference problem. More precisely, the problem may be stated as follows: Given a set of positive sentences I+ a set of negative sentences I? Find the set of all automata A verifying: 1. A is a deterministic nite state automata; 2. I+ is structurally complete for A; 3. L(A), the language accepted by A, does not contain I?; 4. L(A) is a most general language (i.e. no other solution A0 is such that L(A) L(A0 )). Given these conditions, the search space is nite and may be partially ordered. Most of proposed algorithms focus on the production of a single solution. They proceed either with a depth rst strategy (Oncina& Garcia 1992), a beam search strategy (Miclet& de Gentille 1994), or with an optimization method (Dupont 1994). The problem has been proven NP-complete in the worst case (Angluin 1978; Kearns& Valiant 1989). Our approach is related to the version space approach (Mitchell 1982) where all solutions of a learning problem are characterized using two sets: the set S of maximally speci c solutions and the set G of maximally general solutions. In our case, S may be built straightforwardly, using the canonical automata. Building G is much more di cult, due to the size of the search space and, in some case, to the size of G itself.

Introduction

Very few authors have studied the characterization of G. Miclet has proposed in (Miclet& de Gentille 1994) a heuristic algorithm. Preliminary studies have also been tried in the context free case (Vanlehn& Ball 1987; Giordano 1993). When the language of generalization consists of vectors of attribute-value pairs, several authors have proposed to manage an implicit representation of the version space (Hirsh 1992; Nicolas 1993; Sebag 1994). In the same spirit, we propose a compact representation of G, based on the set of admissible merging of states. We show that such a set may be represented with a set of unequality constraints and we give an e cient algorithm to build the elements of G, reducing the problem to the coloring of the graph of constraints. The next section brie y introduces concepts and notations we need to present our results. The third section establishes a constraint characterization of the G set. We propose in the fourth section an algorithm for an e ective production of automata elements of G. The results of a rst experimentation on a classical benchmark are given in the fth section. It is the rst time to our knowledge, that a characterization of the whole set of solutions is proposed for this benchmark. We conclude with a sketch of various tracks of improvement for our work.

Def 1 (DFA) A nite state automata is a quintuplet

Regular Inference: de nitions, notations and theorems

(Q;;; q0; F ) where Q is a nite set of states, an al

phabet, a transition function from Q to 2Q Q ), q is the initial state (extended to Q !2 0 and F Q is the set of accepting or nal states. If 8q 2 Q; 8a 2 (q; a) has at most one element, the automaton is said deterministic and we denote DFA

第1页

你可能喜欢

热门文档

相关文档

  • A coloring problem

    Regular Inference as a g... 暂无评价 6页 免费 Regular inference as a g... 暂无评价 6页 免费 A Graph Coloring Problem... 暂无评价 15页 免费 Cycle...

  • Graph coloring problems and their applications in s...

    Graph coloring problems and their applications in scheduling,” Periodica Polytechnica_专业资料。Graph coloring and its generalizations are useful tools in modeli...

  • ...for solving planar graph coloring problem

    Modified PSO algorithm for solving planar graph coloring problem_专业资料。维普资讯 http://www.cqvip.com Avibeolea、^^sinerc.om all ni t^,fcecditan维普...

  • 外文翻译

    To model register allocation as a graph coloring problem, the compiler first constructs an interference graph G. The nodes in G correspond to live ranges...

  • Hybrid Evolutionary Algorithm for Graph Coloring

    The first heuristic approaches to solving the graph coloring problem, which color the vertices of the graph one by one guided by a greedy function. ? ...

  • unit disk graph

    search A collection of unit circles and the corresponding unit disk graph. ...graph optimization problems such as maximum independent set, graph coloring, ...

  • On graph coloring check-digit method

    On the graph coloring ... 暂无评价 12页 免费 Graph coloring on a co... 暂无评价 11页 免费 Graph coloring on a co... 暂无评价 6页 免费 Graph ...

  • Perfect Graphs and Vertex Coloring Problem

    problem to determine an optimal coloring of a graph is NP-complete in general case.Gr¨tschell and al develo oped polynomial algorithm to solve this ...

  • Graph -- from Wolfram MathWorld

    specified criteria is known as graph coloring [25...[59], Regular Graph [60], Sequential Graph [...Graph Inference from W... 暂无评价 106页 免费 ...

  • ...problem in dense random graphs

    procedure on other NP-complete problems, such as graph partitioning, graph coloring, the traveling salesman problem, inductive inference and linear ordering. ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email