On the definability of properties of finite graphs

DOI10.1016/0012-365X(84)90166-3zbMATH Open0536.05060MaRDI QIDQ791548FDOQ791548

Authors: Gy. Turán 

Publication date: 1984

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complexityHamiltonian graphsdefinability of graph-properties

Mathematics Subject Classification ID

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

Cites Work

• Model theory
• Disjoint paths in graphs
• Title not available (Why is that?)
• Monadic generalized spectra
• Mechanizing hypothesis formation. Mathematical foundations for a general theory
• Number of quantifiers is better than number of tape cells
• The computational complexity of logical theories
• Application of model theoretic games to discrete linear orders and finite automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (20)

• Second-order and Inductive Definability on Finite Structures
• Succinct definitions in the first order theory of graphs
• The closure of monadic NP
• Title not available (Why is that?)
• Finite-model theory -- A personal perspective
• 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
• On winning strategies in Ehrenfeucht-Fraïssé games
• Tarski's theory of definability: Common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic
• 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
• Expressing properties in second- and third-order logic: hypercube graphs and SATQBF

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)