Search

We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs H of a graph G of the neighborhood set system of H is sandwiched between Ω (log ⁡ deg (G)) and O (deg (G)) , where deg (G) denotes the degeneracy of G. We extend this result to inequalities relating weak coloring numbers and discrepancy of graph powers and deduce a new characterization of bounded expansion classes. Then we switch to a model theoretical point of view, introduce pointer structures, and study their relations to graph classes with bounded expansion. We deduce that a monotone class of graphs has bounded expansion if and only if all the set systems definable in this class have bounded hereditary discrepancy. Using known bounds on the VC-density of set systems definable in nowhere dense classes we also give a characterization of nowhere dense classes in terms of discrepancy. As consequences of our results, we obtain a corollary on the discrepancy of neighborhood set systems of edge colored graphs, a polynomial-time algorithm to compute ε -approximations of size O (1 / ε) for set systems definable in bounded expansion classes, an application to clique coloring, and even the non-existence of a quantifier elimination scheme for nowhere dense classes. [ABSTRACT FROM AUTHOR]

This paper is dedicated to studying the algorithmic properties of unars with an injective function. We prove that the theory of every such unar admits quantifier elimination if the language is extended by a countable set of predicate symbols. Necessary and sufficient conditions are established for the quantifier elimination to be effective, and a criterion for decidability of theories of such unars is formulated. Using this criterion, we build a unar such that its theory is decidable, but the theory of the unar of its subsets is undecidable. [ABSTRACT FROM AUTHOR]

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]

We prove some results about the model theory of fields with a derivation of the Frobenius map, especially that the model companion of this theory is axiomatizable by axioms used by Wood in the case of the theory $\operatorname {DCF}_p$ and that it eliminates quantifiers after adding the inverse of the Frobenius map to the language. This strengthens the results from [4]. As a by-product, we get a new geometric axiomatization of this model companion. Along the way we also prove a quantifier elimination result, which holds in a much more general context and we suggest a way of giving "one-dimensional" axiomatizations for model companions of some theories of fields with operators. [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]

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.

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]

We have provided a model-theoretic proof for the decidability of the additive structure of integers together with the function f mapping x to ⌊ φ x ⌋ where φ is the golden ratio. [ABSTRACT FROM AUTHOR]

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.

An interesting application of a method of quantifier elimination in epidemiology was presented in this paper. The existence of the endemic equilibrium was investigated for several epidemic models, the SEIR, MSEIR and MSEIRS. Also, a value of the endemic equilibrium was calculated for these models. An interesting application of the SEIR model is that it was analyzed with the concrete values through the example of Ebola in three different countries. In order to complete the paper, a new virus covid-19 was considered and it was pointed out that the SIR and the SEIR model are not appropriate for it because of some unusual characteristics of covid-19. So, in the literature can be seen numerous different models applied to a new virus, such as SIQR, SVIR, their modifications and many others. [ABSTRACT FROM AUTHOR]

This article presents results and open problems related to definability spaces (reducts) and sources of this field since the 19th century. Finiteness conditions and constraints are investigated, including the depth of quantifier alternation and the number of arguments. Results related to the description of lattices of definability spaces for numerical and other natural structures are described. Research methods include the study of automorphism groups of elementary extensions of the structures under consideration, application of the Svenonius theorem. [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.

Copyright of Automatisierungstechnik is the property of De Gruyter and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

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]

The problems of finding accurate limits of integration in symbolic form are non-trivial when analyzing the secrecy outage probability (SOP) over complicated communication schemes. To identify these limits, we formulate an existential quantifier elimination (QE) problem based on the description of the secrecy outage events. After that, the resulting QE problem can be solved using QE algorithms such as cylindrical algebraic decomposition (CAD) via existing solvers. Since CAD is an exact algorithm, our approach does not require Monte-Carlo simulations to verify the correctness of the SOP integration limits. Finally, two complex SOP analysis scenarios for cognitive radio systems are presented to demonstrate the generality of the proposed method. [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 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.

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 show that the quantifier elimination result for the Shelah-Spencer almost sure theories of sparse random graphs G (n , n - α) given by Laskowski (Isr J Math 161:157–186, 2007) extends to their various analogues. The analogues will be obtained as theories of generic structures of certain classes of finite structures with a notion of strong substructure induced by rank functions and we will call the generics Baldwin–Shi hypergraphs. In the process we give a method of constructing extensions whose 'relative rank' is negative but arbitrarily small in context. We give a necessary and sufficient condition for the theory of a Baldwin–Shi hypergraph to have atomic models. We further show that for certain well behaved classes of theories of Baldwin–Shi hypergraphs, the existentially closed models and the atomic models correspond. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

Quantum communication channels suffer from various noises, which are mathematically modeled by error super-operators. To combat these errors, it is necessary to design recovery super-operators. We aim to construct the optimal recovery that maximizes the minimum fidelity through the noisy channel. It is typically a MAX–MIN problem, out of the scope of convex optimization. Compared to existing methods, our method is exact and complete by a reduction to quantifier elimination over real closed fields in a fragment of two alternative quantifier blocks. Finally, the complexity is shown to be in EXP. [ABSTRACT FROM AUTHOR]

This paper is dedicated to studying decidability properties of theories of regular languages with classical operations: union, concatenation, and the Kleene star. The theory with union only is a theory of some Boolean algebra, so it is decidable. We prove that the theory of regular languages with the Kleene star only is decidable. If we use union and concatenation simultaneously, then the theory becomes both Σ1- and π1-hard over the one-symbol alphabet. Using methods from the proof of this theorem we establish that the theory of regular languages over one-symbol alphabet with union and the Kleene star is as hard as arithmetic. Then we establish that the theory with all three operations is reducible to arithmetic also, hence, it is equivalent to arithmetic. Finally, we prove that the theory of regular languages over any alphabet with concatenation only is equivalent to arithmetic also. The last result is based on our previous work where an analogous theorem was proved for one-symbol languages. [ABSTRACT FROM AUTHOR]