On Finding a First-Order Sentence Consistent with a Sample of Strings

Thiago Alves Rocha
(Federal Institute of Ceará)
Ana Teresa Martins
(Federal University of Ceará)
Francicleber Martins Ferreira
(Federal University of Ceará)

We investigate the following problem: given a sample of classified strings, find a first-order sentence of minimal quantifier rank that is consistent with the sample. We represent strings as successor string structures, that is, finite structures with unary predicates to denote symbols in an alphabet, and a successor relation. We use results of the Ehrenfeucht-Fraïssé game over successor string structures in order to design an algorithm to find such sentence. We use conditions characterizing the winning strategies for the Spoiler on successor strings structures in order to define formulas which distinguish two strings. Our algorithm returns a boolean combination of such formulas.

In Andrea Orlandini and Martin Zimmermann: Proceedings Ninth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2018), Saarbrücken, Germany, 26-28th September 2018, Electronic Proceedings in Theoretical Computer Science 277, pp. 220–234.
Published: 7th September 2018.

ArXived at: https://dx.doi.org/10.4204/EPTCS.277.16 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org