The Complexity of Defining a Relation on a Finite Graph

DOI10.1002/MALQ.19870330312MaRDI QIDQ3778739zbMATH OpenOpenAlexFDO

Authors László Babai, Gy. Turán

Publication date 1987

Published in Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19870330312

zbMATH Keywords

3-regular asymmetric graphsdefinability of relations on finite graphs by short formulasquantifier rank

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Graph theory (05C99)

Recommendations

• On the definability of properties of finite graphs
• Descriptive complexity of finite structures: Saving the quantifier rank
• Succinct definitions in the first order theory of graphs
• The first order definability of graphs: Upper bounds for quantifier depth
• Logical complexity of graphs: a survey

Cited in

(12)

• Farrell polynomials on graphs of bounded tree width
• Tree-width and the monadic quantifier hierarchy.
• Two consequences of the dichotomy theorem on first order definability of graphs.
• Succinct definitions in the first order theory of graphs
• Defining relations for deterministic graphs
• Logical complexity of graphs: a survey
• Relative expressiveness of the edge/adjacency language for graph theory
• On the Encoding of Relations by Graphs
• Second-order and Inductive Definability on Finite Structures
• Expressibility of properties of relations
• Descriptive complexity of finite structures: Saving the quantifier rank
• On the definability of properties of finite graphs

This page was built for publication: The Complexity of Defining a Relation on a Finite Graph

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