Search

In this study, we tackle the subject of interval quadratic equations and we aim to accurately determine the root enclosures of quadratic equations, whose coefficients constitute interval variables. This study focuses on interval quadratic equations that contain only one coefficient considered as an interval variable. The four methods reviewed here in order to solve this problem are: (i) the method of classic interval analysis used by Elishakoff and Daphnis, (ii) the direct method based on minimizations and maximizations also used by the same authors, (iii) the method of quantifier elimination used by Ioakimidis, and (iv) the interval parametrization method suggested by Elishakoff and Miglis and again based on minimizations and maximizations. We will also compare the results yielded by all these methods by using the computer algebra system Mathematica for computer evaluations (including quantifier eliminations) in order to conclude which method would be the most efficient way to solve problems relevant to interval quadratic equations. [ABSTRACT FROM AUTHOR]

This paper deals with systematic approaches for the analysis of stability properties and controller design for nonlinear dynamical systems. Numerical methods based on sum-of-squares decomposition or algebraic methods based on quantifier elimination are used. Starting from Lyapunov's direct method, these methods can be used to derive conditions for the automatic verification of Lyapunov functions as well as for the structural determination of control laws. This contribution describes methods for the automatic verification of (control) Lyapunov functions as well as for the constructive determination of control laws. [ABSTRACT FROM AUTHOR]

We consider a first-order logic for the integers with addition. This logic extends classical first-order logic by modulo-counting, threshold-counting and exact-counting quantifiers, all applied to tuples of variables (here, residues are given as terms while moduli and thresholds are given explicitly). Our main result shows that satisfaction for this logic is decidable in two-fold exponential space. If only threshold- and exact-counting quantifiers are allowed, we prove an upper bound of alternating two-fold exponential time with linearly many alternations. This latter result almost matches Berman's exact complexity of first-order logic without counting quantifiers. To obtain these results, we first translate threshold- and exact-counting quantifiers into classical first-order logic in polynomial time (which already proves the second result). To handle the remaining modulo-counting quantifiers for tuples, we first reduce them in doubly exponential time to modulo-counting quantifiers for single elements. For these quantifiers, we provide a quantifier elimination procedure similar to Reddy and Loveland's procedure for first-order logic and analyse the growth of coefficients, constants, and moduli appearing in this process. The bounds obtained this way allow to restrict quantification in the original formula to integers of bounded size which then implies the first result mentioned above. Our logic is incomparable with the logic considered by Chistikov et al. in 2022. They allow more general counting operations in quantifiers, but only unary quantifiers. The move from unary to non-unary quantifiers is non-trivial, since, e.g., the non-unary version of the Härtig quantifier results in an undecidable theory. [ABSTRACT FROM AUTHOR]

Pseudo o-minimality is a generalization of o-minimality of linear orders to partial orders. Recently Lei Chen, Niandong Shi and Guohua Wu provided pseudo o-minimality for the class of Stone algebras. In this note we use quantifier elimination property to show that the class of double Stone algebras is pseudo o-minimal in their expanded language.

In this paper, we study bounded versions of some model-theoretic notions and results. We apply these results to the context of models of bounded arithmetic theories as well as some related complexity questions. As an example, we show that if the theory \(\rm S_2 ^1(PV)\) has bounded model companion then \(\rm NP=coNP\). We also study bounded versions of some other related notions such as Stone topology.

This paper deals with systematic approaches for the analysis of stability properties and controller design for nonlinear dynamical systems. Numerical methods based on sum-of-squares decomposition or algebraic methods based on quantifier elimination are used. Starting from Lyapunov’s direct method, these methods can be used to derive conditions for the automatic verification of Lyapunov functions as well as for the structural determination of control laws. This contribution describes methods for the automatic verification of (control) Lyapunov functions as well as for the constructive determination of control laws.

Abstract We show that positivity (≥0) on R + n $\mathbb{R}_{+}^{n}$ and on R n $\mathbb{R}^{n}$ of real symmetric polynomials of degree at most p in n ≥ 2 $n\ge 2$ variables is solvable by algorithms running in polynomial time in the number n of variables. For real symmetric quartics, we find discriminants which lead to the efficient algorithms QE4+ and QE4 running in O ( n ) $O(n)$ time. We describe the Maple implementation of both algorithms, which are then used not only for testing concrete inequalities (with given numerical coefficients and number of variables), but also for proving symbolic inequalities.

In this paper, we study bounded versions of some model-theoretic notions and results. We apply these results to models of bounded arithmetic theories as well as some related complexity questions. As an example, we show that if the theory S2¹(PV) has bounded model companion then NP = coNP. We also study bounded versions of some other related notions such as Stone topology. [ABSTRACT FROM AUTHOR]

We present a framework for tame geometry on Henselian valued fields, whichwe call Henselminimality. In the spirit of o-minimality, which is key to real geometry and several diophantine applications, we develop geometric results and applications for Hensel minimal structures that were previously known only under stronger, less axiomatic assumptions. We show the existence of t-stratifications in Hensel minimal structures and Taylor approximation results that are key to non-Archimedean versions of Pila-Wilkie point counting, Yomdin's parameterization results and motivic integration. In this first paper, we work in equi-characteristic zero; in the sequel paper, we develop the mixed characteristic case and a diophantine application. [ABSTRACT FROM AUTHOR]

We study systems of relations of the form A x σ b , where σ is a vector of binary relations with the components " = ", " ≥ ", and " ≤ ", while the parameters (elements of the matrix A and right-hand side vector b) are uncertain and can take values from prescribed intervals. What is considered to be the set of its solutions depends on which logical quantifier is associated with each interval-valued parameter and what is the order of the quantifier prefixes for specific parameters. For solution sets that correspond to the quantifier prefix of a general form, we present equivalent quantifier-free analytical descriptions in the classical interval arithmetic, in Kaucher complete interval arithmetic and in the usual real arithmetic. [ABSTRACT FROM AUTHOR]

We present a framework for tame geometry on Henselian valued fields, which we call Hensel minimality. In the spirit of o-minimality, which is key to real geometry and several diophantine applications, we develop geometric results and applications for Hensel minimal structures that were previously known only under stronger, less axiomatic assumptions. We show the existence of t-stratifications in Hensel minimal structures and Taylor approximation results that are key to non-Archimedean versions of Pila–Wilkie point counting, Yomdin’s parameterization results and motivic integration. In this first paper, we work in equi-characteristic zero; in the sequel paper, we develop the mixed characteristic case and a diophantine application.

The inference of program invariants over machine arithmetic, commonly called bit-vector arithmetic, is an important problem in verification. Techniques that have been successful for unbounded arithmetic, in particular Craig interpolation, have turned out to be difficult to generalise to machine arithmetic: existing bit-vector interpolation approaches are based either on eager translation from bit-vectors to unbounded arithmetic, resulting in complicated constraints that are hard to solve and interpolate, or on bit-blasting to propositional logic, in the process losing all arithmetic structure. We present a new approach to bit-vector interpolation, as well as bit-vector quantifier elimination (QE), that works by lazy translation of bit-vector constraints to unbounded arithmetic. Laziness enables us to fully utilise the information available during proof search (implied by decisions and propagation) in the encoding, and this way produce constraints that can be handled relatively easily by existing interpolation and QE procedures for Presburger arithmetic. The lazy encoding is complemented with a set of native proof rules for bit-vector equations and non-linear (polynomial) constraints, this way minimising the number of cases a solver has to consider. We also incorporate a method for handling concatenations and extractions of bit-vector efficiently. [ABSTRACT FROM AUTHOR]

We show that positivity (≥0) on R + n and on R n of real symmetric polynomials of degree at most p in n ≥ 2 variables is solvable by algorithms running in polynomial time in the number n of variables. For real symmetric quartics, we find discriminants which lead to the efficient algorithms QE4+ and QE4 running in O (n) time. We describe the Maple implementation of both algorithms, which are then used not only for testing concrete inequalities (with given numerical coefficients and number of variables), but also for proving symbolic inequalities. [ABSTRACT FROM AUTHOR]

It is well-known that the central path of semi-definite optimization, unlike linear optimization, has no analytic extension to μ = 0 in the absence of the strict complementarity condition. In this paper, we consider a reparametrization μ ↦ μ ρ , with ρ being a positive integer, that recovers the analyticity of the central path at μ = 0. We investigate the complexity of computing ρ using algorithmic real algebraic geometry and the theory of complex algebraic curves. We prove that the optimal ρ is bounded by 2 O (m 2 + n 2 m + n 4) , where n is the matrix size and m is the number of affine constraints. Our approach leads to a symbolic algorithm, based on the Newton-Puiseux algorithm, which computes a feasible ρ using 2 O (m + n 2) arithmetic operations. [ABSTRACT FROM AUTHOR]

Timed pushdown automata (tpda) are an expressive formalism combining recursion with a rich logic of timing constraints. We prove that reachability relations of tpda are expressible in linear arithmetic, a rich logic generalising Presburger arithmetic and rational arithmetic. The main technical ingredients are a novel quantifier elimination result for clock constraints (used to simplify the syntax of tpda transitions), the use of clock difference relations to express reachability relations of the fractional clock values, and an application of Parikh's theorem to reconstruct the integral clock values. [ABSTRACT FROM AUTHOR]

Assume that K is a field and I1 ... ... ... It is an ascending chain (of length t) of ideals in the polynomial ring K[x1, ..., xm], for some m ≥ 1. Suppose that Ij is generated by polynomials of degrees less or equal to some natural number f(j) ≥ 1, for any j = 1, ..., t. In the paper we construct, in an elementary way, a natural number B(m, f) (depending on m and the function f) such that t ≤ B(m, f). We also discuss some applications of this result. [ABSTRACT FROM AUTHOR]

Forgetting is an important concept in knowledge representation and automated reasoning with widespread applications across a number of disciplines. A standard forgetting operator, characterized in [26] in terms of model-theoretic semantics and primarily focusing on the propositional case, opened up a new research subarea. In this paper, a new operator called weak forgetting , dual to standard forgetting, is introduced and both together are shown to offer a new more uniform perspective on forgetting operators in general. Both the weak and standard forgetting operators are characterized in terms of entailment and inference, rather than a model theoretic semantics. This naturally leads to a useful algorithmic perspective based on quantifier elimination and the use of Ackermann's Lemma and its fixpoint generalization. The strong formal relationship between standard forgetting and strongest necessary conditions and weak forgetting and weakest sufficient conditions is also characterized quite naturally through the entailment-based, inferential perspective used. The framework used to characterize the dual forgetting operators is also generalized to the first-order case and includes useful algorithms for computing first-order forgetting operators in special cases. Practical examples are also included to show the importance of both weak and standard forgetting in modeling and representation. [ABSTRACT FROM AUTHOR]

Color coding is an algorithmic technique used in parameterized complexity theory to detect “small” structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pattern. We transfer color coding to the world of descriptive complexity theory by characterizing—purely in terms of the syntactic structure of describing formulas—when the powerful second-order quantifiers representing a random coloring can be replaced by equivalent, simple first-order formulas. Building on this result, we identify syntactic properties of first-order quantifiers that can be eliminated from formulas describing parameterized problems. The result applies to many packing and embedding problems, but also to the long path problem. Together with a new result on the parameterized complexity of formula families involving only a fixed number of variables, we get that many problems lie in FPT just because of the way they are commonly described using logical formulas.

We are concerned with rigid analytic geometry in the general setting of Henselian fields K with separated analytic structure, whose theory was developed by Cluckers−Lipshitz−Robinson. It unifies earlier work and approaches of numerous mathematicians. Separated analytic structures admit reasonable relative quantifier elimination in a suitable analytic language. However, the rings of global analytic functions with two kinds of variables seem not to have good algebraic properties such as Noetherianity or excellence. Therefore, the usual global resolution of singularities from rigid analytic geometry is no longer at our disposal. Our main purpose is to give a definable version of the canonical desingularization algorithm (the hypersurface case) due to Bierstone−Milman so that both of these powerful tools are available in the realm of non-Archimedean analytic geometry at the same time. It will be carried out within a category of definable, strong analytic manifolds and maps, which is more flexible than that of affinoid varieties and maps. Strong analytic objects are those definable ones that remain analytic over all fields elementarily equivalent to K. This condition may be regarded as a kind of symmetry imposed on ordinary analytic objects. The strong analytic category makes it possible to apply a model-theoretic compactness argument in the absence of the ordinary topological compactness. On the other hand, our closedness theorem enables application of resolution of singularities to topological problems involving the topology induced by valuation. Eventually, these three results will be applied to such issues as the existence of definable retractions or extending continuous definable functions. The established results remain valid for strictly convergent analytic structures, whose classical examples are complete, rank one valued fields with the Tate algebras of strictly convergent power series. The earlier techniques and approaches to the purely topological versions of those issues cannot be carried over to the definable settings because, among others, non-Archimedean geometry over non-locally compact fields suffers from lack of definable Skolem functions.

This paper presents a framework to derive instantiation-based decision procedures for satisfiability of quantified formulas in first-order theories, including its correctness, implementation, and evaluation. Using this framework we derive decision procedures for linear real arithmetic and linear integer arithmetic formulas with one quantifier alternation. We discuss extensions of these techniques for handling mixed real and integer arithmetic, and to formulas with arbitrary quantifier alternations. For the latter, we use a novel strategy that handles quantified formulas that are not in prenex normal form, which has advantages with respect to existing approaches. All of these techniques can be integrated within the solving architecture used by typical SMT solvers. Experimental results on standardized benchmarks from model checking, static analysis, and synthesis show that our implementation in the SMT solver cvc4 outperforms existing tools for quantified linear arithmetic. [ABSTRACT FROM AUTHOR]

Several criteria for mixed-mode fracture in crack problems are based on the maximum of a quantity quite frequently related to stress components. This quantity should not reach a critical value. Computationally, this approach requires the use of the first and the second derivatives of the above quantity although frequently the use of the second derivative is omitted because of the necessary complicated computations. Therefore, mathematically, the determination of the maximum of the quantity of interest is not assured when the classical approach is used without the second derivative. Here a completely different and more rigorous approach is proposed. The present approach is based on symbolic computations and makes use of modern quantifier elimination algorithms implemented in the computer algebra system Mathematica. The maximum tangential stress criterion, the generalized maximum tangential stress criterion (with a T-stress term), the T-criterion and the modified maximum energy release rate criterion are used for the illustration of the present new approach in the mode I/II case. Beyond the conditions of fracture initiation, the determination of the fracture angle is also studied. The mode I/III case is also considered in brief. The present approach completely avoids differentiations, similarly the necessity of a distinction between maxima and minima, always leads to a global (absolute) and not to a local (relative) maximum and frequently to closed-form formulae and automatically makes a distinction of cases in the final formula whenever this is necessary. Moreover, its use is easy and direct and the maximum of the quantity of interest is always assured. [ABSTRACT FROM AUTHOR]

We describe a new quantifier elimination algorithm for real closed fields based on Thom encoding and sign determination. The complexity of this algorithm is elementary recursive and its proof of correctness is completely algebraic. In particular, the notion of connected components of semialgebraic sets is not used. [ABSTRACT FROM AUTHOR]

Let R = ( R , ⊕ , ≤ , 0 ) be an algebraic structure, where ⊕ is a commutative binary operation with identity 0, and ≤ is a translation-invariant total order with least element 0. Given a distinguished subset S ⊆ R , we define the natural notion of a “generalized” R -metric space, with distances in S . We study such metric spaces as first-order structures in a relational language consisting of a distance inequality for each element of S . We first construct an ordered additive structure S ⁎ on the space of quantifier-free 2-types consistent with the axioms of R -metric spaces with distances in S , and show that, if A is an R -metric space with distances in S , then any model of Th ( A ) logically inherits a canonical S ⁎ -metric. Our primary application of this framework concerns countable, universal, and homogeneous metric spaces, obtained as generalizations of the rational Urysohn space. We adapt previous work of Delhommé, Laflamme, Pouzet, and Sauer to fully characterize the existence of such spaces. We then fix a countable totally ordered commutative monoid R , with least element 0, and consider U R , the countable Urysohn space over R . We show that quantifier elimination for Th ( U R ) is characterized by continuity of addition in R ⁎ , which can be expressed as a first-order sentence of R in the language of ordered monoids. Finally, we analyze an example of Casanovas and Wagner in this context. [ABSTRACT FROM AUTHOR]

The derivation on the differential-valued field T log of logarithmic transseries induces on its value group Γ log a certain map ψ . The structure ( Γ log , ψ ) is a divisible asymptotic couple. We prove that the theory T log = Th ( Γ log , ψ ) admits elimination of quantifiers in a natural first-order language. All models ( Γ , ψ ) of T log have an important discrete subset Ψ : = ψ ( Γ ∖ { 0 } ) . We give explicit descriptions of all definable functions on Ψ and prove that Ψ is stably embedded in Γ. [ABSTRACT FROM AUTHOR]

Linear equalities, disequalities and inequalities on fixed-width bit-vectors, collectively called linear modular constraints, form an important fragment of the theory of fixed-width bit-vectors. We present a practically efficient and bit-precise algorithm for quantifier elimination from conjunctions of linear modular constraints. Our algorithm uses a layered approach, whereby sound but incomplete and cheaper layers are invoked first, and expensive but complete layers are called only when required. We then extend this algorithm to work with arbitrary Boolean combinations of linear modular constraints as well. Experiments on an extensive set of benchmarks demonstrate that our techniques significantly outperform alternative quantifier elimination techniques based on bit-blasting and linear integer arithmetic. [ABSTRACT FROM AUTHOR]

We present an algorithm which computes a cylindrical algebraic decomposition of a semialgebraic set using projection sets computed for each cell separately. Such local projection sets can be significantly smaller than the global projection set used by the Cylindrical Algebraic Decomposition (CAD) algorithm. This leads to reduction in the number of cells the algorithm needs to construct. A restricted version of the algorithm was introduced in Strzeboński (2014) . The full version presented here can be applied to quantified formulas and makes use of equational constraints. We give an empirical comparison of our algorithm and the classical CAD algorithm. [ABSTRACT FROM AUTHOR]

A quantifier elimination algorithm by cylindrical algebraic decomposition based on regular chains is presented. The main idea is to refine a complex cylindrical tree until the signs of polynomials appearing in the tree are sufficient to distinguish the true and false cells. We report an implementation of our algorithm in the RegularChains library in Maple and illustrate its effectiveness by examples. [ABSTRACT FROM AUTHOR]