Questions tagged [first-order-logic]
The first-order-logic tag has no usage guidance.
42
questions
6
votes
1
answer
174
views
Bounded Star Height and corresponding fragments of MSO
The generalized star height of a regular language is defined as the maximal number of nested Kleene-stars in a regular expression (with union, concatenation, complement, and Kleene-stars) that ...
- 197
3
votes
0
answers
56
views
Open source implementations of euclidean geometery automated theorem provers
I plan to work on extending a theorem prover which is specialised in generating proofs for questions based in euclidean geometry which is taught to high school students to introduce them to the ideas ...
- 31
-1
votes
2
answers
157
views
Help understand why FOL wff are enumerable, but FOL is undecidable
I am very new to this. I am trying to understand some basics about what kinds of enumerations in FOL are possible, and which are not.
If you accept that FOL is defined in terms of a finite number of ...
- 107
8
votes
1
answer
369
views
In logic programming, what would a language with second-order model theory gain?
HiLog is described as a logic programming language with higher-order syntax, but first-order model theory.
For example, it allows you to define a map over lists:
...
- 259
1
vote
0
answers
46
views
Are classes of graphs represented by adjacency matrix ordered structures?
We know that FO[LFP] captures PTIME on the class of ordered structures. However, I have difficulties interpreting this result. From what I understand, it means that, given a constant, finite alphabet $...
-3
votes
1
answer
112
views
Can one do descriptive complexity theory using abstract state machines?
I learned about ASM recently and was interested how it could used for descriptive complexity theory.
Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. ...
- 315
1
vote
0
answers
61
views
Elimination of monadic second-order quantifiers
I'm trying to understand what is currently known to be possible regarding the elimination of monadic second-order quantifiers. Many sources cite that monadic second-order logic supports elimination of ...
- 1,734
2
votes
1
answer
94
views
Second-order reachability in second-order logic
By second-order reachability I mean a second-order lifting of the reachability problem on first-order structures. So let $R(X,Y)$ be a second-order binary predicate (i.e. it links a set of elements $X$...
- 1,734
0
votes
2
answers
103
views
Inexpressibility results for first-order logic that fail extending the language
Think of the classical inexpressivity results that one studies in early courses about first-order logic, e.g. that on a signature with a binary predicate $R$ one cannot express that $R$ is connected. ...
- 1,734
4
votes
1
answer
59
views
References on second-order quantifier elimination and related topics
I was wondering whether something like elimination of second-order quantifiers exist, and indeed it seems it does. I've found there's a workshop on this topic, and the webpage describes exactly what I ...
- 1,734
0
votes
0
answers
77
views
Number of quantifier alternations in prenex form of a formula
I'm currently studying hyperlogics and in particular HyperLTL/CTL*.
In model checking algorithms for such logics the number of quantifier alternations appearing in a formula can play an important role ...
- 101
1
vote
0
answers
77
views
Do soundness and completeness need to be exact converses of eachother?
This question concerns the derivational soundness and completeness of the first-order proof system LK (without equality) as presented in Logical Foundations of Proof Complexity by Cook and Nguyen. In ...
- 201
1
vote
1
answer
83
views
Why isn't the proof obtained using Buss's proof of the derivational completeness of LK anchored?
The version of Buss's proof I'm referring to is the proof of Lemma II.2.24 in Logical Foundations of Proof Complexity by Cook and Nguyen. In the interest of keeping this question self-contained I've ...
- 201
0
votes
1
answer
118
views
Number of equivalent formulas in a function-free first order logic language?
In this paper by Martin Grohe, in the first paragraph of section 4.1, it says:
"because upto logical equivalence there only exist finitely many $FO[\rho]$ formulas of quantifier rank at most $q$ ...
- 716
0
votes
1
answer
73
views
Resources for first-order and second-order monadic logics with a model-checking objective
What are some good books and surveys for learning about first-order logic and monadic second-order logic?
I'm a graduate student in computer science with a focus on algorithms. For model-checking on ...
- 45
0
votes
1
answer
91
views
reducing this problem to a decision problem
Before I can define my problem, let's make a simple definition. An expression $e$ is a conjunction of inequalities of the form $x~ op~ v$ where: $x$ is a variable, $op\in[<,>,\leq,\geq,=]$, and $...
- 13
1
vote
0
answers
168
views
What is the model of computation that corresponds (in the manner of Curry-Howard) to the deduction rule of resolution?
The Curry-Howard Correspondence is well-documented for the isomorphism which associates the intuitionistic natural deduction proof calculus (logic side) with the type system for the simply typed ...
- 109
4
votes
0
answers
86
views
Are there classes for that FO-model checking is FPT on hypergraphs?
For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al.
Are there similar results for ($k$-uniform)...
- 41
3
votes
3
answers
517
views
Evaluating asymptotic probabilities of First Order Logic Formulas?
0-1 Laws in first order logic state that the probability of a FOL sentence $\Phi$, defined as follows:
$$P(\Phi) = \frac{|\{\omega \in \Omega^{n}:\omega \models \Phi\}|}{|\Omega^{n}|} $$
where $\Omega^...
- 716
9
votes
1
answer
159
views
Validity problem of intuitionistic two-variable logic
The two-variable fragment $\mathrm{FO}^2$ consist of those sentences of first-order logic $\mathrm{FO}$ in which precisely two variables occur (e.g. $\exists x \exists y \exists z R(x,y,z)$ is not a ...
- 1,099
3
votes
2
answers
160
views
Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals [closed]
Looking for some lecture videos (introductory level) on logic, models of computation as well as computational complexity/ other theoretical computer science fundamentals
- 228
2
votes
2
answers
166
views
Tableau method for two-variable first-order logic
$FO^2$, i.e. two-variable first-order logic, has a NEXPTIME-complete satisfiability problem (see Grädel, Kolaitis and Vardi '97). However, the decidability and complexity of this fragment is proved by ...
- 1,734
2
votes
1
answer
236
views
Scott's normal form for $\exists y \forall x R(x,y) $
In this paper Scott's reduction is discussed, which reduces any FO2 formula to Scott's Normal form. As far as I understand the reduction process explained in the paper can get you to formulas with ...
- 716
0
votes
0
answers
53
views
How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?
In the following paper the author's claim that almost all graphs can be expressed in first order logic with counting quantifiers and two variables.
I would like to know, is there any algorithm that ...
- 716
2
votes
2
answers
248
views
A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm?
I'm looking for an explanation of critical pairs and the Knuth-Bendix completion algorithm that is at once rigorous and of high pedagogical value, i.e. clear, detailed, containing illustrative ...
- 354
1
vote
0
answers
106
views
How does complexity of a counting problem influence wether it admits a closed form formula or not?
In https://arxiv.org/abs/1412.1505, the section "Results on Data Complexity" mentions the fact that since the authors are about to proove $\#P_1$ complexity for weighted model counting in ...
- 716
2
votes
0
answers
174
views
Order-invariant conjunctive queries are FO-definable without the order
I'm looking for a reference for Exercise 6.11 from Libkin's FMT book:
Prove that an order-invariant conjunctive query is FO-definable without the order relation.
All help is appreciated.
- 1,377
2
votes
1
answer
186
views
Is Scott's reduction sound for $\mathrm{FO}^2$ with equality?
As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the ...
- 716
3
votes
1
answer
184
views
Normal forms for counting quantifiers?
In the paper by [Erich Grädel and Martin Otto], the authors state that any formula in First Order Logic with two variables with counting quantifiers can be reduced to a formula of the form
$$ \forall ...
- 716
9
votes
1
answer
351
views
Existing implementation of Scott's reduction?
As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the ...
- 716
1
vote
2
answers
210
views
Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates?
This question has inspired the following two questions.
Given a first order logic language, with only unary predicates, finite number of variables, $\forall$ and $\exists$ i.e no equality and ...
- 716
1
vote
0
answers
111
views
Constructing FOL formula for which counting is easy?
Given a function free First Order Logic language $\mathcal{L}$ are there ways to write formulas for which counting the number of models for a given cardinality of the domain is easy (preferably exists ...
- 716
6
votes
3
answers
626
views
Can modern SAT-Solvers utilise the symmetry of First Order Logic?
Apologies if the question is trivial or is wrongly stated, I am a Physicist!
Assuming that we have a universally quantified first-order logic sentence, all variables are universally quantified, ...
- 716
7
votes
1
answer
399
views
Kleene Algebra for star-free regular expressions
TLDR: Is there a notion of Kleene Algebra for star-free regular expressions?
Kleene Algebras are algebraic structures that are equivalent to regular expressions. A Kleene Algebra is an idempotent ...
- 203
4
votes
1
answer
242
views
The theory of definitions in first order logic
I'm looking for a clear and thorough treatment of the theory of definitions in first order predicate logic from a syntactic/proof theoretic point of view (as opposed to semantic/model theoretic point ...
- 354
4
votes
1
answer
149
views
A first order logic extended with binding terms like the familiar set descriptors $\{x:\varphi\}$
First order logic comes equipped with two kinds of terms:
Variable: those terms of the form $x$ for some variable $x$, of which there are infinite.
Function application: those terms of the form $f(...
- 354
6
votes
0
answers
402
views
Reverse Skolemization?
I'm wondering if there are any references on "reverse skolemization", that is, converting a formula with functions into one purely consisting of quantifiers by eliminating function applications.
I'm ...
- 2,952
11
votes
0
answers
234
views
Descriptive Complexity characterzation of BPP
We know of descriptive complexity characterizations of classes such as P, and NP, which use First Order logic, and operators. Does BPP have a characterization under descriptive complexity, too(any ...
- 1,261
3
votes
0
answers
47
views
Extending the sequential calculus (logic over words) to allow a hierarchy of languages like the arithmetical hierarchy
Let $\Sigma$ be some finite alphabet. Then consider the logical language $\mathcal L = \{ R_a : a \in \Sigma \} \cup \{ <,= \}$ and first order formulas. For a given first order formula $\varphi$ a ...
- 2,057
1
vote
0
answers
151
views
Proof of SAT is complete for NP via first-order reductions
So I have been reading this: https://people.cs.umass.edu/~immerman/book/ch7.pdf
I do not understand the proof of theorem 7.16, which says that SAT is complete for NP via first-order reductions. My ...
- 21
12
votes
2
answers
461
views
State of the Art for the Monadic Class?
Monadic First Order Logic, also known as the Monadic Class of the Decision Problem, is where all predicates take one argument. It was shown to be decidable by Ackermann, and is NEXPTIME-complete.
...
- 2,952
12
votes
1
answer
278
views
For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?
I want to be very specific. Does anyone know of a disproof or a proof of the following proposition:
$\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$
$\forall G, H \in STRUC[\Sigma_{graph}] (...
- 1,582