Search results for "03D15"

showing 3 items of 3 documents

The fluted fragment with transitive relations

2022

Abstract The fluted fragment is a fragment of first-order logic (without equality) in which, roughly speaking, the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that this fragment has the finite model property. We consider extensions of the fluted fragment with various numbers of transitive relations, as well as the equality predicate. In the presence of one transitive relation (together with equality), the finite model property is lost; nevertheless, we show that the satisfiability and finite satisfiability problems for this extension remain decidable. We also show that the corresponding problems in the…

FOS: Computer and information sciencesComputer Science - Logic in Computer ScienceTransitivityTransitive relationLogicFinite model propertyF.4.1; F.2.2DecidabilityExtension (predicate logic)SatisfiabilityLogic in Computer Science (cs.LO)DecidabilityUndecidable problemFluted logicCombinatoricsFragment (logic)03D15F.4.1Order (group theory)F.2.2SatisfiabilityMathematicsAnnals of Pure and Applied Logic
researchProduct

Topological Logics with Connectedness over Euclidean Spaces

2013

We consider the quantifier-free languages, Bc and Bc °, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of being connected, and the property of having a connected interior. These languages are interpreted over the regular closed sets of R n ( n ≥ 2) and, additionally, over the regular closed semilinear sets of R n . The resulting logics are examples of formalisms that have recently been proposed in the Artificial Intelligence literature under the rubric Qualitative Spatial Reasoning. We prove that the satisfiability problem for Bc is undecidable over the regular closed semilinear sets in all dimensions greater than 1,…

FOS: Computer and information sciencesComputer Science - Logic in Computer ScienceGeneral Computer ScienceUnary operationClosed setLogicSocial connectedness0102 computer and information sciencesTopological space68T30 (Primary) 03D15 68Q17 (Secondary)Topology01 natural sciencesTheoretical Computer ScienceMathematics - Geometric TopologyEuclidean geometryFOS: Mathematics0101 mathematicsMathematicsI.2.4; F.4.3; F.2.2Discrete mathematicsI.2.4010102 general mathematicsGeometric Topology (math.GT)Predicate (mathematical logic)Undecidable problemLogic in Computer Science (cs.LO)Computational Mathematics010201 computation theory & mathematicsF.4.3F.2.2Boolean satisfiability problemACM Transactions of Computational Logic
researchProduct

Exact quantum algorithms have advantage for almost all Boolean functions

2014

It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that ${AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.

FOS: Computer and information sciencesNuclear and High Energy Physics81P68 03D15Parity functionBoolean circuitGeneral Physics and AstronomyFOS: Physical sciencesBoolean algebras canonically definedComputational Complexity (cs.CC)Theoretical Computer ScienceCombinatoricsBoolean expressionBoolean functionMathematical PhysicsComputer Science::DatabasesMathematicsDiscrete mathematicsSymmetric Boolean functionQuantum PhysicsProduct termComputer Science::Information RetrievalStatistical and Nonlinear PhysicsComputer Science - Computational ComplexityComputational Theory and MathematicsMaximum satisfiability problemQuantum Physics (quant-ph)
researchProduct