Search results for "First-Order logic"

showing 2 items of 22 documents

Two-variable First-Order Logic with Counting in Forests

2018

We consider an extension of two-variable, first-order logic with counting quantifiers and arbitrarily many unary and binary predicates, in which one distinguished predicate is interpreted as the mother-daughter relation in an unranked forest. We show that both the finite satisfiability and the general satisfiability problems for the extended logic are decidable in NExpTime. We also show that the decision procedure for finite satisfiability can be extended to the logic where two distinguished predicates are interpreted as the mother-daughter relations in two independent forests.

Variable (computer science)general satisfiabilityfinite satisfiabilitylogic and computational complexitydecision proceduresArithmetictwo-variable logic with counting quantifiersunranked trees/forestsMathematicsFirst-order logicEPiC Series in Computing
researchProduct

Games and Bisimulations for Intuitionistic First-Order Kripke Models

2021

The aim of this paper is to introduce the notion of a game for intuitionisticfirst-order Kripke models. We also establish links between notions presented here and thenotions of logical equivalence and bounded bisimulation for intuitionistic first-order Kripkemodels, and the Ehrenfeucht–Fra ̈ıss ́e game for classical first-order structures.

Winning strategyBisimulationLogical equivalenceLogicIntuitionistic first-order logicKripke modelsGameEhrenfeucht–Fra ̈ıss ́e gameFirst orderAlgebraHistory and Philosophy of ScienceBounded functionComputational linguisticsKripke modelMathematicsStudia Logica
researchProduct