On the definability of properties of finite graphs

DOI10.1016/0012-365X(84)90166-3MaRDI QIDQ791548zbMATH OpenFDO

Authors Gy. Turán

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexityHamiltonian graphsdefinability of graph-properties

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph theory (05C99) General logic (03B99)

Recommendations

• The Complexity of Defining a Relation on a Finite Graph
• Succinct definitions in the first order theory of graphs
• Logical complexity of graphs: a survey
• scientific article; zbMATH DE number 2101962
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cites work

• scientific article; zbMATH DE number 3754050 (Why is no real title available?)
• scientific article; zbMATH DE number 3784267 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• Application of model theoretic games to discrete linear orders and finite automata
• Disjoint paths in graphs
• Mechanizing hypothesis formation. Mathematical foundations for a general theory
• Model theory
• Monadic generalized spectra
• Number of quantifiers is better than number of tape cells
• The computational complexity of logical theories

Cited in

(20)

• Expressing properties in second- and third-order logic: hypercube graphs and SATQBF
• Second-order and Inductive Definability on Finite Structures
• Succinct definitions in the first order theory of graphs
• The closure of monadic NP
• Finite-model theory -- A personal perspective
• scientific article; zbMATH DE number 6256303 (Why is no real title available?)
• Logical complexity of graphs: a survey
• Properties of Almost All Graphs and Generalized Quantifiers
• Descriptive complexity of finite structures: Saving the quantifier rank
• Context-Free Graph Properties via Definable Decompositions
• Tarski's theory of definability: Common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic
• On winning strategies in Ehrenfeucht-Fraïssé games
• Two consequences of the dichotomy theorem on first order definability of graphs.
• AN ALTERNATIVE WAY OF DEFINING FINITE GRAPHS
• Arity and alternation in second-order logic
• On winning strategies with unary quantifiers
• Annotation theories over finite graphs
• First-order logic axiomatization of metric graph theory
• The Complexity of Defining a Relation on a Finite Graph
• Some Remarks on Definability of Process Graphs

This page was built for publication: On the definability of properties of finite graphs

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