# Questions tagged [finite-model-theory]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
1answer
69 views

### How to describe Deterministic Transitive Closure in FOL?

In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE. Hence, taking into account that ...
0answers
21 views

### About quasi-linear finite automata

Let M a finite state transducer define as : $M=<X,Y,S,\delta,\lambda>$ What we mean by quasi-linear finite automata?
2answers
71 views

### Defining $a^n b^{n^2}$ with one existential SO binary relation

Is it possible to define the language: $$L = \{ a^n \; b^{n^2} \}$$ using an existential second order sentence over strings (ordered structures with unary predicates $U_a(x), U_b(x)$) using only ...
0answers
68 views

### Datalog Program Equivalence with Fixed Universe Size

It is well known that to compute equivalence of two Datalog programs (or equivalently of two first order formulas with the least fixed point operator) wrt all possible inputs and universes, is ...
0answers
51 views

### LTL and alternation

Apparently, model checking LTL on Kripke structures is PSPACE-complete (see this question). Usually, when something in finite model theory is PSPACE-hard, there is a simple proof using the APTIME ...
1answer
248 views

### Datalog Self Interpretation

According to https://link.springer.com/article/10.1007%2Fs001530050135 (Logics that define their own semantics, Imhof 1999) the logic FO[LFP] can define its own semantics, though the proof (of ...
1answer
44 views

2answers
903 views

### Does the 'difference' operation add expressiveness to a query language that already includes 'join'?

The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases ...