-
-
We study the decidability problem for metric and layered temporal logics. The
logics we consider are suitable to model time granularity in various contexts,
and they allow one to build granular temporal models by referring to the
`natural scale' in any component of the model and by properly co...
-
This paper focuses on decidability problems for metric and layered temporal
logics which allow one to model time granularity in various contexts. The
decidability of pure metric (nongranular) fragments and of metric temporal
logics endowed with finitely many layers has been already proved by ...
-
In this paper, we generalize the settheoretic translation method for
polymodal logic introduced in [11] to extended modal logics. Instead of
devising an adhoc translation for each logic, defining a new settheoretic
function symbol for each new modal operator, we develop a general framework ...
-
We prove that in the Solovay model every OD graph G on reals satisfies
one and only one of the following two conditions: (I) G admits an OD
colouring by ordinals; (II) there exists a continuous homomorphism of G_0
into G; where G 0 is a certain F_sigma locally countable graph which is not
ROD co...
-
We present a simple and completely modeltheoretical proof of a strengthening
of a theorem of Ajtai's: the independence of the pigeonhole principle from
I-\Delta_0(R). Qua strength, the theorem proved here corresponds to the
complexity/prooftheoretical results of [10] and [14] but a different...
-
Preservation and interpolation results are obtained for L_{\infty\omega}
and sublogics L \subseteq L_{\infty\omega} such that equivalence in L can
be characterized by suitable backandforth conditions on sets of partial
isomorphisms.
-
We will show in this paper that there is no interpolation theorem for
the fragment of pure equivalence in intuitionistic propositional logic.
The computer program that was used to calculate the counterexample
by computations on a finite Kripke model is briefly sketched.
-
-
We consider two families of modal logics of relations: arrow logic and
cylindric modal logic and several natural expansions of these, interpreted
on a range of (relativised) modelclasses. We give a systematic study
of the complexity of the validity problem of these logics, obtaining
price ta...
-
We prove the Lyndon Theorem and the Łoś–Tarski Theorem for the modal \mucalculus, using automata which run on process graphs and are equivalent in expressive power to the \mucalculus.