Paper Info
Title
Synthesis of a DNF Formula from a Sample of Strings using Ehrenfeucht–Fraïssé Games
Abstract
In order to define a DNF version of first-order sentences over strings in which atomic sentences represent substring properties of strings, we use results of the Ehrenfeucht–Fraïssé game over strings. Then, given a sample of strings and the number of disjunctive clauses, we investigate the problem of finding a DNF formula that is consistent with the sample. We show that this problem is NP-complete, and we solve it by a translation into Boolean satisfiability. We also present an extension of this problem that is robust concerning noisy samples. We solve the generalized version by a codification into the maximum satisfiability problem. As first-order logic over strings defines exactly the class of locally threshold testable (LTT) languages, our results can be useful in the grammatical inference framework when the goal is to find a model of a LTT language from a sample of strings.
Year
DOI
Venue
2020
10.1016/j.tcs.2019.08.015
Theoretical Computer Science
Keywords
Field
DocType
Formula synthesis,Grammatical inference,Ehrenfeucht–Fraïssé games
Maximum satisfiability problem,Discrete mathematics,Combinatorics,Substring,Grammar induction,Boolean satisfiability problem,Mathematics
Journal
Volume
ISSN
Citations 
805
0304-3975
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Thiago Alves Rocha100.68
Ana Teresa Martins224.80
Francicleber Martins Ferreira314.44