Results 1 to 10 of about 165,682 (186)

On the Union Closed Fragment of Existential Second-Order Logic and Logics with Team Semantics [PDF]

Logical Methods in Computer Science, 2021
We present syntactic characterisations for the union closed fragments of existential second-order logic and of logics with team semantics. Since union closure is a semantical and undecidable property, the normal form we introduce enables the handling and
Matthias Hoelzel, Richard Wilke
doaj   +5 more sources

The succinctness of first-order logic on linear orders [PDF]

Logical Methods in Computer Science, 2005
Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all properties that can be expressed in L_2 can be expressed in L_1 by formulas of (approximately) the ...
Martin Grohe, Nicole Schweikardt
doaj   +6 more sources

Propositional Logics Complexity and the Sub-Formula Property [PDF]

Electronic Proceedings in Theoretical Computer Science, 2015
In 1979 Richard Statman proved, using proof-theory, that the purely implicational fragment of Intuitionistic Logic (M-imply) is PSPACE-complete.
Edward Hermann Haeusler
doaj   +5 more sources

Multiplicative-Additive Proof Equivalence is Logspace-complete, via Binary Decision Trees [PDF]

Logical Methods in Computer Science, 2017
Given a logic presented in a sequent calculus, a natural question is that of equivalence of proofs: to determine whether two given proofs are equated by any denotational semantics, ie any categorical interpretation of the logic compatible with its cut ...
Marc Bagnol
doaj   +3 more sources

Alternating Quantifiers in Uniform One-Dimensional Fragments with an Excursion into Three-Variable Logic [PDF]

Logical Methods in Computer Science
The uniform one-dimensional fragment of first-order logic was introduced a few years ago as a generalization of the two-variable fragment to contexts involving relations of arity greater than two.
Oskar Fiuk, Emanuel Kieronski
doaj   +5 more sources

Loop-free verification of termination of derivation for a fragment of dynamic logic

Lietuvos Matematikos Rinkinys, 2008
A fragment of a deterministic propositional dynamic logic (DPDL, in short) is considered The language of considered fragment contains propositional symbols, action constants, action operator (repetition) and logical symbols.
Regimantas Pliuškevičius
doaj   +3 more sources

Decision procedure for a fragment of quantified branching temporal logic

Lietuvos Matematikos Rinkinys, 2002
There is not abstract.
Aida Pliuškevičienė
doaj   +5 more sources

Negational Fragment of Intuitionistic Control Logic [PDF]

, 2014
We investigate properties of monadic purely negational fragment of Intuitionistic Control Logic (ICL). This logic arises from Intuitionistic Propositional Logic (IPL) by extending language of IPL by additional new constant for falsum.
Anna Glenszczyk
openalex   +6 more sources

Loop-check free sequent calculi for unary fragment of temporal logic

Lietuvos Matematikos Rinkinys
This paper explores the construction of an efficient sequent calculus for a selected fragment of porpositional linear temporal logic (PLTL), extending the ideas of classical calculi discussed in [1], and builds upon previous investigations into the ...
Lukas Maksimiak, Adomas Birštunas
doaj   +3 more sources

Modal meet-implication logic [PDF]

Logical Methods in Computer Science, 2022
We extend the meet-implication fragment of propositional intuitionistic logic with a meet-preserving modality. We give semantics based on semilattices and a duality result with a suitable notion of descriptive frame.
Jim de Groot, Dirk Pattinson
doaj   +1 more source