Let f(z)=nFn−1(α,β) be the hypergeometric series with parameters α=(α1,…,αn) and β=(β1,…,βn−1,1) in (Q∩(0,1)n, let dα,β be the least common multiple of the denominators of α1,…,αn, β1,…,βn−1 written ...in lowest form and let p be a prime number such that p does not divide dα,β and f(z)∈Z(p)z. Recently in 11, it was shown that if for all i,j∈{1,…,n}, αi−βj∉Z then the reduction of f(z) modulo p is algebraic over Fp(z). A standard way to measure the complexity of an algebraic power series is to estimate its degree and its height. In this work, we prove that if p>2dα,β then there is a nonzero polynomial Pp(Y)∈Fp(z)Y having degree at most p2nφ(dα,β) and height at most 5n(n+1)!p2nφ(dα,β) such that Pp(f(z)modp)=0, where φ is the Euler's totient function. Furthermore, our method of proof provides us a way to make an explicit construction of the polynomial Pp(Y). We illustrate this construction by applying it to some explicit hypergeometric series.
In symbolic regression with formal constraints, the conventional formulation of regression problem is extended with desired properties of the target model, like symmetry, monotonicity, or convexity. ...We present a genetic programming algorithm that solves such problems using a Satisfiability Modulo Theories solver to formally verify the candidate solutions. The essence of the method consists in collecting the counterexamples resulting from model verification and using them to improve search guidance. The method is exact: upon successful termination, the produced model is guaranteed to meet the specified constraints. We compare the effectiveness of the proposed method with standard constraint-agnostic machine learning regression algorithms on a range of benchmarks, and demonstrate that it outperforms them on several performance indicators.
Secure state estimation is the problem of estimating the state of a dynamical system from a set of noisy and adversarially corrupted measurements. Intrinsically a combinatorial problem, secure state ...estimation has been traditionally addressed either by brute force search, suffering from scalability issues, or via convex relaxations, using algorithms that can terminate in polynomial time but are not necessarily sound. In this paper, we present a novel algorithm that uses a satisfiability modulo theory approach to harness the complexity of secure state estimation. We leverage results from formal methods over real numbers to provide guarantees on the soundness and completeness of our algorithm. Moreover, we discuss its scalability properties, by providing upper bounds on the runtime performance. Numerical simulations support our arguments by showing an order of magnitude decrease in execution time with respect to alternative techniques. Finally, the effectiveness of the proposed algorithm is demonstrated by applying it to the problem of controlling an unmanned ground vehicle.
Let q be a power of the prime number p, let K=Fq(t), and let r⩾2 be an integer. For points a,b∈K which are Fq-linearly independent, we show that there exist positive constants N0 and c0 such that for ...each integer ℓ⩾N0 and for each generator τ of Fqℓ/Fq, we have that for all except N0 values λ∈Fq‾, the corresponding specializations a(τ) and b(τ) cannot have orders of degrees less than c0loglogℓ as torsion points for the Drinfeld module Φ(τ,λ):FqT⟶EndFq‾(Ga) (where Ga is the additive group scheme), given by ΦT(τ,λ)(x)=τx+λxq+xqr.
Structured learning modulo theories Teso, Stefano; Sebastiani, Roberto; Passerini, Andrea
Artificial intelligence,
March 2017, 2017-03-00, 20170301, Volume:
244
Journal Article
Peer reviewed
Open access
Modeling problems containing a mixture of Boolean and numerical variables is a long-standing interest of Artificial Intelligence. However, performing inference and learning in hybrid domains is a ...particularly daunting task. The ability to model these kinds of domains is crucial in “learning to design” tasks, that is, learning applications where the goal is to learn from examples how to perform automatic de novo design of novel objects. In this paper we present Structured Learning Modulo Theories, a max-margin approach for learning in hybrid domains based on Satisfiability Modulo Theories, which allows to combine Boolean reasoning and optimization over continuous linear arithmetical constraints. The main idea is to leverage a state-of-the-art generalized Satisfiability Modulo Theory solver for implementing the inference and separation oracles of Structured Output SVMs. We validate our method on artificial and real world scenarios.
We present a new method for the automated synthesis of digital controllers with formal safety guarantees for systems with nonlinear dynamics, noisy output measurements, and stochastic disturbances. ...Our method derives digital controllers such that the corresponding closed-loop system, modeled as a sampled-data stochastic control system, satisfies a safety specification with probability above a given threshold. Our technique uses a fast solver and an optimization method to search for candidate controllers, which are then formally evaluated in closed-loop with the system in question by a verified solver. Unstable candidate controllers are discarded by efficiently checking a sufficient condition for Lyapunov stability of sampled-data nonlinear systems. We evaluate our technique on three case studies: an artificial pancreas model, a powertrain control model, and a quadruple-tank process.
Quantum annealers (QAs) are specialized quantum computers that minimize objective functions over discrete variables by physically exploiting quantum effects. Current QA platforms allow for the ...optimization of quadratic objectives defined over binary variables (qubits), also known as Ising problems. In the last decade, QA systems as implemented by D-Wave have scaled with Moore-like growth. Current architectures provide 2048 sparsely-connected qubits, and continued exponential growth is anticipated, together with increased connectivity.
We explore the feasibility of such architectures for solving SAT and MaxSAT problems as QA systems scale. We develop techniques for effectively encoding SAT –and, with some limitations, MaxSAT– into Ising problems compatible with sparse QA architectures. We provide the theoretical foundations for this mapping, and present encoding techniques that combine offline Satisfiability and Optimization Modulo Theories with on-the-fly placement and routing. Preliminary empirical tests on a current generation 2048-qubit D-Wave system support the feasibility of the approach for certain SAT and MaxSAT problems.
PDF
