The two‐variable fragment with counting and equivalence

We consider the two‐variable fragment of first‐order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime ‐complete. We further show that the corresponding problems for two‐variable first‐order logic with counting and two equivalences are both undecidable.     

Finite satisfiability for two‐variable,first‐order logic with one transitive relation is decidable

We consider two‐variable, first‐order logic in which a single distinguished predicate is required to be interpreted as a transitive relation. We show that the finite satisfiability problem for this logic is decidable in triply exponential non‐deterministic time. Complexity falls to doubly exponential non‐deterministic time if the transitive relation is constrained to be a partial order.     

Undecidability results on two-variable logics

It is a classical result of Mortimer that , first-order logic with two variables, is decidable for satisfiability. We show that going beyond by adding any one of the following leads to an undecidable logic:– very weak forms of recursion, viz.?(i) transitive closure operations?(ii) (restricted) monadic fixed-point operations?– weak access to cardinalities, through the H?rtig (or equicardinality) quantifier?– a choice construct known as Hilbert's -operator. In fact all these extensions of prove to be undecidable both for satisfiability, and for satisfiability in finite structures. Moreover most of them are hard for , the first level of the analytical hierachy, and thus have a much higher degree of undecidability than first-order logic. Received: 13 July 1996     

Sémantique de type Kripke d'un système logique basé sur un ensemble ordonné fini

In order to modelize the reasoning of intelligent agents represented by a poset T, H. Rasiowa introduced logic systems called “Approximation Logics”. In these systems the use of a set of constants constitutes a fundamental tool. We have introduced in [8] a logic system called without this kind of constants but limited to the case that T is a finite poset. We have proved a completeness result for this system w.r.t. an algebraic semantics. We introduce in this paper a Kripke‐style semantics for a subsystem of for which there existes a deduction theorem. The set of “possible worldsr is enriched by a family of functions indexed by the elements of T and satisfying some conditions. We prove a completeness result for system with respect to this Kripke semantics and define a finite Kripke structure that characterizes the propositional fragment of logic . We introduce a reational semantics (found by E. Orlowska) which has the advantage to allow an interpretation of the propositionnal logic using only binary relations. We treat also the computational complexity of the satisfiability problem of the propositional fragment of logic .     

Semidefinite resolution and exactness of semidefinite relaxations for satisfiability

This paper explores new connections between the satisfiability problem and semidefinite programming. We show how the process of resolution in satisfiability is equivalent to a linear transformation between the feasible sets of the relevant semidefinite programming problems. We call this transformation semidefinite programming resolution, and we demonstrate the potential of this novel concept by using it to obtain a direct proof of the exactness of the semidefinite formulation of satisfiability without applying Lasserre’s general theory for semidefinite relaxations of 0/1 problems. In particular, our proof explicitly shows how the exactness of the semidefinite formulation for any satisfiability formula can be interpreted as the implicit application of a finite sequence of resolution steps to verify whether the empty clause can be derived from the given formula.     

Nontransitive temporal multiagent logic,information and knowledge,deciding algorithms

Multiagent and temporal logics are active domains in Information Sciences, CS, and AI. Attention has predominantly focused on the logics based on transitive relational models, with particular emphasis on transitive time. But this does not seem rather reliable assumption. Nontransitivity of passing information may be demonstrated with relative ease through persuasive examples. Therefore, we introduce and study multiagent temporal logics that are based on nontransitive linear time. Another innovative step is consideration of incomplete information: the information/knowledge with lacunas,—the linear time with forgettable intervals of time in the past. Technically, the most important problems are problems of satisfiability and decidability of suggested logics. The main results are the algorithms that compute satisfiability and solve decidability (and so provide solutions to these problems). The paper concludes by posing a series of open problems.     

EIN NEUER BEWEIS UND EINE VERSCHÄRFUNG FÜR DEN REDUKTIONSTYP ∀∃∀∞(0, 1) MIT EINER ANWENDUNG AUF DIE SPEKTRALE DARSTELLUNG VON PRÄDIKATEN

A simultaneous semantical and syntactical reduction is given for the satisfiability respectively finite satisfiability of first order formulas. We choose ???∞(0, 1) as conservative reduction class and allow only formulas out of ???∞(0, 1) having a simple set theoretical model if they are satisfiable at all. With the same method we get a spectral representation of any ?-ary enumerable respectively coenumerable predicate by a formula out of ???∞(?, 1).     

Computational complexity of some restricted instances of 3-SAT

Tovey [A simplified satisfiability problem, Discrete Appl. Math. 8 (1984) 85-89] showed that it is NP-hard to decide the satisfiability of 3-SAT instances in which every variable occurs four times, while every instance of 3-SAT in which each variable occurs three times is satisfiable. We explore the border between these two problems. Answering a question of Iwama and Takaki, we show that, for every fixed k?0, there is a polynomial-time algorithm to determine the satisfiability of 3-SAT instances in which k variables occur four times and the remaining variables occur three times. On the other hand, it is NP-hard to decide the satisfiability of 3-SAT instances in which all but one variable occurs three times, and the remaining variable is allowed to occur an arbitrary number of times.     

Design of Interpolating Biorthogonal Multiwavelet Systems with Compact Support

In this paper we characterize all totally interpolating biorthogonal finite impulse response (FIR) multifilter banks of multiplicity two, and provide a design framework for corresponding compactly supported multiwavelet systems with high approximation order. In these systems, each component of the analysis and synthesis portions possesses the interpolating property. The design framework is based on scalar filter banks, and examples with approximation order two and three are provided. We show that our multiwavelet systems preserve almost all of the desirable properties of the generalized interpolating scalar wavelet systems, including the dyadic-rational nature of the filter coefficients, equality of the flatness degree of the low-pass filters and the approximation order of the corresponding functions, and equality between the uniform samples of a signal and its projection coefficients for a given scale. This last property allows us to avoid the cumbersome prefiltering associated with standard multiwavelet systems. We also show that there are no symmetric totally interpolating biorthogonal multifilter banks of multiplicity two. Finally, we point out that our design framework incorporates a simple relationship between the multiscaling functions and multiwavelets that substantially simplifies the implementation of the system.     

Satisfiability of algebraic circuits over sets of natural numbers

We investigate the complexity of satisfiability problems for {∪,∩,⁻,+,×}-circuits computing sets of natural numbers. These problems are a natural generalization of membership problems for expressions and circuits studied by Stockmeyer and Meyer (1973) [10] and McKenzie and Wagner (2003) [8].Our work shows that satisfiability problems capture a wide range of complexity classes such as NL, P, NP, PSPACE, and beyond. We show that in several cases, satisfiability problems are harder than membership problems. In particular, we prove that testing satisfiability for {∩,+,×}-circuits is already undecidable. In contrast to this, the satisfiability for {∪,+,×}-circuits is decidable in PSPACE.     

On homeomorphisms with the two-sided limit shadowing property

We prove that the two-sided limit shadowing property is among the strongest known notions of pseudo-orbit tracing. It implies shadowing, average shadowing, asymptotic average shadowing and specification properties. We also introduce a weaker notion that is called two-sided limit shadowing with a gap and prove that it implies shadowing and transitivity. We show that those two properties allow to characterize topological transitivity and mixing in a class of expansive homeomorphisms and hence they characterize transitive (mixing) shifts of finite type.     

Interpolation in superintuitionistic predicate logics with equality

It is shown that the Craig interpolation property and the Beth property are preserved under passage from a superintuitionistic predicate logic to its extension via standard axioms for equality, and under adding formulas of pure equality as new axioms. We find an infinite independent set of formulas which, though not equivalent to formulas of pure equality, may likewise be added as new axiom schemes without loss of the interpolation, or Beth, property. The formulas are used to construct a continuum of logics with equality, which are intermediate between the intuitionistic and classical ones, having the interpolation property. Moreover, an equality-free fragment of the logics constructed is an intuitionistic predicate logic, and formulas of pure equality satisfy all axioms of the classical predicate logic. Supported by RFFR grant No. 96-01-01552. Translated fromAlgebra i Logika, Vol. 36, No. 5, pp. 543–561, September–October, 1997.     

Satisfiability of formulae with one ∀ is decidable in exponential time

Summary In first order logic without equality, but with arbitrary relations and functions the ^** class is the unique maximal solvable prefix class. We show that the satisfiability problem for this class is decidable in deterministic exponential time The result is established by a structural analysis of a particular infinite subset of the Herbrand universe and by a polynomial space bounded alternating procedure.This work was done while the author was staying at the University of Pisa, Italy, and was supported by the Swiss National Science Foundation     

Untangling comparison bias in inductive item tree analysis based on representative random quasi-orders

Inductive item tree analysis (IITA) comprises three data analysis algorithms for deriving quasi-orders to represent reflexive and transitive precedence relations among binary variables. In previous studies, when comparing the IITA algorithms in simulations, the representativeness of the sampled quasi-orders was not considered or implemented only unsatisfactorily. In the present study, we show that this issue yields non-representative samples of quasi-orders, and thus biased or incorrect conclusions about the performance of the IITA algorithms used to reconstruct underlying relational dependencies. We report the results of a new, truly representative simulation study, which corrects for these problems and that allows the algorithms to be compared in a reliable manner.     

Geometric conditions for Kuhn–Tucker sufficiency of global optimality in mathematical programming

We present geometric criteria for a feasible point that satisfies the Kuhn–Tucker conditions to be a global minimizer of mathematical programming problems with or without bounds on the variables. The criteria apply to multi-extremal programming problems which may have several local minimizers that are not global. We establish such criteria in terms of underestimators of the Lagrangian of the problem. The underestimators are required to satisfy certain geometric property such as the convexity (or a generalized convexity) property. We show that the biconjugate of the Lagrangian can be chosen as a convex underestimator whenever the biconjugate coincides with the Lagrangian at a point. We also show how suitable underestimators can be constructed for the Lagrangian in the case where the problem has bounds on the variables. Examples are given to illustrate our results.     

Bose–Einstein condensation in satisfiability problems

This paper is concerned with the complex behavior arising in satisfiability problems. We present a new statistical physics-based characterization of the satisfiability problem. Specifically, we design an algorithm that is able to produce graphs starting from a k-SAT instance, in order to analyze them and show whether a Bose–Einstein condensation occurs. We observe that, analogously to complex networks, the networks of k-SAT instances follow Bose statistics and can undergo Bose–Einstein condensation. In particular, k-SAT instances move from a fit-get-rich network to a winner-takes-all network as the ratio of clauses to variables decreases, and the phase transition of k-SAT approximates the critical temperature for the Bose–Einstein condensation. Finally, we employ the fitness-based classification to enhance SAT solvers (e.g., ChainSAT) and obtain the consistently highest performing SAT solver for CNF formulas, and therefore a new class of efficient hardware and software verification tools.     

On the predecessor relation in abstract algebras

In this paper we generalize the Dedekind theory of order for the natural numbers N to abstract algebras with arbitrarily many finitary or infinitary operations. For any algebra ??, we introduce an algebraic predecessor relation P?? and its transitive hull P*?? coinciding in N with the unary injective successor function' resp. the >-relation. For some important classes of algebras ??, including Peano algebras (absolutely free algebras, word algebras), the algebraic predecessor relation is well-founded. Hence, its transitive hull, the natural ordering >?? of ??, is a well-founded partial order, which turns out to be a convenient device for classifying Peano algebras with respect to the number of operations and their arities. Moreover, the property of well-foundedness is an efficient tool for giving simple proofs of structure theorems as, e. g., that the class of all Peano algebras is closed under subalgebras and non-void direct products. - Finally, we will show how in the case of a formal language ??, i. e., the Peano algebra ?? of expressions (= terms & formulas), relations P??, resp. P*_?? can be used to define basic syntactical notions as occurences of free and bound variables etc. without any reference to a particular representation (“coding”) of the formal language. MSC: 03B22, 03E30, 03E75, 03F35, 08A55, 08B20.     

Models and quantifier elimination for quantified Horn formulas

In this paper, quantified Horn formulas (QHORN) are investigated. We prove that the behavior of the existential quantifiers depends only on the cases where at most one of the universally quantified variables is zero. Accordingly, we give a detailed characterization of QHORN satisfiability models which describe the set of satisfying truth assignments to the existential variables. We also consider quantified Horn formulas with free variables (QHORN^*) and show that they have monotone equivalence models.The main application of these findings is that any quantified Horn formula Φ of length |Φ| with free variables, |∀| universal quantifiers and an arbitrary number of existential quantifiers can be transformed into an equivalent quantified Horn formula of length O(|∀|·|Φ|) which contains only existential quantifiers.We also obtain a new algorithm for solving the satisfiability problem for quantified Horn formulas with or without free variables in time O(|∀|·|Φ|) by transforming the input formula into a satisfiability-equivalent propositional formula. Moreover, we show that QHORN satisfiability models can be found with the same complexity.     

Shadowing, entropy and minimal subsystems

We consider non-wandering dynamical systems having the shadowing property, mainly in the presence of sensitivity or transitivity, and investigate how closely such systems resemble the shift dynamical system in the richness of various types of minimal subsystems. In our excavation, we do discover regularly recurrent points, sensitive almost 1-1 extensions of odometers, minimal systems with positive topological entropy, etc. We also show that transitive semi-distal systems with shadowing are in fact minimal equicontinuous systems (hence with zero entropy) and, in contrast to systems with shadowing, the entropy points do not have to be densely distributed in transitive systems.