<p>Suppose $\sigma$ is a vocabulary consisting of one binary relation $E$ and let $\phi$ be a $\sigma$ sentence. Is it decidable whether there is a finite directed graph $G$, with all in- and out-degrees $0$ or $1$, such that $G\models \phi$ ?</p>

CC BY-SA 3.0
2013-03-10T15:44:19.427Z
This is a very elementary question, and not of the level usually answered here.  Read any basic text on Finite Model Theory and you should know the answer.
Marc Hamann
CC BY-SA 3.0
2013-03-11T04:48:54.797Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.
Kaveh
<graph-algorithms><finite-model-theory>
Decidability one relation, binary FOL over finite models
pritam
# Decidability one relation, binary FOL over finite models

(Asked by: username_0 on 2013-03-10)

Suppose $\sigma$ is a vocabulary consisting of one binary relation $E$ and let $\phi$ be a $\sigma$ sentence. Is it decidable whether there is a finite directed graph $G$, with all in- and out-degrees $0$ or $1$, such that $G\models \phi$ ?

**Tags:** graph-algorithms, finite-model-theory
> **Comments:**
> **username_1**: This is a very elementary question, and not of the level usually answered here.  Read any basic text on Finite Model Theory and you should know the answer.  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.  

---

## 0 answers

