On distinguishing sets of structures by first-order sentences of minimal quantifier rank

DOI10.1016/J.ENTCS.2019.07.012MaRDI QIDQ2333677zbMATH OpenOpenAlexWikidataFDO

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

Publication date 13 November 2019

Full work available at URL https://doi.org/10.1016/j.entcs.2019.07.012

zbMATH Keywords

distinguishabilityEhrenfeucht-Fraïssé gamesfinite model theory

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Analysis of algorithms (68W40)

Recommendations

• On complexity of Ehrenfeucht-Fraïssé games
• On Complexity of Ehrenfeucht-Fraïssé Games
• Descriptive complexity of finite structures: Saving the quantifier rank
• Games on Trees and Syntactical Complexity of Formulas
• An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures

Cites work

• A Complete Axiomatization for Blocks World
• An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures
• An application of games to the completeness problem for formalized theories
• Application of model theoretic games to discrete linear orders and finite automata
• Classifying regular events in symbolic logic
• Elements of finite model theory.
• Exact DFA Identification Using SAT Solvers
• Experiments with reduction finding
• Finding All Minimum-Size DFA Consistent with Given Examples: SAT-Based Approach
• Games on Strings with a Limited Order Relation
• scientific article; zbMATH DE number 1342211 (Why is no real title available?)
• scientific article; zbMATH DE number 6999908 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 930362 (Why is no real title available?)
• scientific article; zbMATH DE number 2201583 (Why is no real title available?)
• Inductive logic programming
• Inductive Logic Programming: Theory and methods
• Learning first-order definable concepts over structures of small degree
• Logical and Relational Learning
• On complexity of Ehrenfeucht-Fraïssé games
• On finding a first-order sentence consistent with a sample of strings
• On the complexity of blocks-world planning
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(5)

• Descriptive complexity of finite abelian groups
• On finding a first-order sentence consistent with a sample of strings
• On first-order sentences without finite models
• Descriptive complexity of finite structures: Saving the quantifier rank
• Minimal first-order structures

This page was built for publication: On distinguishing sets of structures by first-order sentences of minimal quantifier rank

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