Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT

DOI10.1016/J.TCS.2020.08.032MaRDI QIDQ2003999zbMATH OpenOpenAlexFDO

Authors Thiago Alves Rocha, Ana Teresa Martins, Francicleber Martins Ferreira

Publication date 13 October 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.08.032

zbMATH Keywords

grammatical inferenceBoolean satisfiabilityEhrenfeucht-Fraïssé games

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational learning theory (68Q32) Model theory of finite structures (03C13) Grammars and rewriting systems (68Q42) Computational aspects of satisfiability (68R07)

Recommendations

• Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games
• Minimal consistent DFA from sample strings
• On complexity of Ehrenfeucht-Fraïssé games
• On Complexity of Ehrenfeucht-Fraïssé Games
• Games on Trees and Syntactical Complexity of Formulas

Cites work

• scientific article; zbMATH DE number 7447745 (Why is no real title available?)
• scientific article; zbMATH DE number 5510691 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• A SAT-based approach to learn explainable decision sets
• A continuous approach to inductive inference
• An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures
• An application of games to the completeness problem for formalized theories
• BFS-based symmetry breaking predicates for DFA identification
• Classifying regular events in symbolic logic
• Cognitive and sub-regular complexity
• Complexity of automaton identification from given data
• Efficient algorithms for the inference of minimum size DFAs
• Efficient symmetry breaking for SAT-based minimum DFA inference
• Exact DFA Identification Using SAT Solvers
• Grammatical inference. Algorithms, routines and applications
• Inference of regular languages using state merging algorithms with search
• Learning subregular classes of languages with factored deterministic automata
• On separation by locally testable and locally threshold testable languages
• Regular inference as vertex coloring
• Solving SAT and SAT modulo theories, from an abstract Davis-Putnam-Logemann-Loveland procedure to \(\operatorname{DPLL}(T)\)
• Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games

Cited in

(1)

• Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games

Describes a project that uses

Uses Software

• PicoSAT

This page was built for publication: Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003999)