Multi-weighted Automata and MSO Logic

Weighted automata are non-deterministic automata where the transitions are equipped with weights. They can model quantitative aspects of systems like costs or energy consumption. The value of a run can be computed, for example, as the maximum, average, or discounted sum of transition weights. In multi-weighted automata, transitions carry several weights and can model, for example, the ratio between rewards and costs, or the efficiency of use of a primary resource under some upper bound constraint on a secondary resource. Here, we introduce a general model for multi-weighted automata as well as a multi-weighted MSO logic. In our main results, we show that this multi-weighted MSO logic and multi-weighted auto-mata are expressively equivalent both for finite and infinite words. The translation process is effective, leading to decidability results for our multi-weighted MSO logic.     

Linear Quantifier Elimination

This paper presents verified quantifier elimination procedures for dense linear orders (two of them novel), for real and for integer linear arithmetic. All procedures are defined and verified in the theorem prover Isabelle/HOL, are executable and can be applied to HOL formulae themselves (by reflection). The formalization of the different theories is highly modular.     

Quantifier Alternation in First-Order Formulas with Infinite Spectra

The spectrum of a first-order formula is the set of numbers α such that for a random graph in a binomial model where the edge probability is a power function of the number of graph vertices with exponent ?α the truth probability of this formula does not tend to either zero or one. In 1990 J. Spenser proved that there exists a first-order formula with an infinite spectrum. We have proved that the minimum quantifier depth of a first-order formula with an infinite spectrum is either 4 or 5. In the present paper we find a wide class of first-order formulas of depth 4 with finite spectra and also prove that the minimum quantifier alternation number for a first-order formula with an infinite spectrum is 3.     

Extensions of MSO and the monadic counting hierarchy

In this paper, we study the expressive power of the extension of first-order logic by the unary second-order majority quantifier Most¹. In 1 it was shown that the extension of FO by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. We consider first certain sublogics of FO(Most¹) over unary vocabularies. We show that over unary vocabularies the logic MSO(R), where MSO is monadic second-order logic and R is the first-order Rescher quantifier, can be characterized by Presburger arithmetic, whereas the logic MSO(Rⁿ)_n∈Z+, where Rⁿ is the nth vectorization of R, corresponds to the Δ₀-fragment of arithmetic. Then we show that FO(Most¹)?MSO(Rⁿ)_n∈Z+ and that, on unary vocabularies, FO(Most¹) collapses to uniform-TC⁰. Using this collapse, we show that first-order logic with the binary second-order majority quantifier is strictly more expressive than FO(Most¹) over the empty vocabulary. On the other hand, over strings, FO(Most¹) is shown to capture the linear fragment of the counting hierarchy. Finally we show that, over non-unary vocabularies, FO(Most¹) can express problems complete via first-order reductions for each level of the counting hierarchy.     

MSO logics for weighted timed automata

We aim to generalize Büchi’s fundamental theorem on the coincidence of recognizable and MSO-definable languages to a weighted timed setting. For this, we investigate weighted timed automata and show how we can extend Wilke’s relative distance logic with weights taken from an arbitrary semiring. We show that every formula in our logic can effectively be transformed into a weighted timed automaton, and vice versa. The results indicate the robustness of weighted timed automata and may also be used for specification purposes.     

Parallel Time and Quantifier Prefixes

We characterize the amount of alternation between blocks of Boolean quantifiers (having both existential and universal), blocks of real existential quantifiers, and blocks of real universal quantifiers that can be decided in parallel polynomial time over the reals. We do so under the assumption that blocks have a uniform bound on their size, both for the case of this bound to be polynomial and constant. On the way towards this characterization we prove a real version of Savitch’s Theorem.     

Quantifier Elimination and Provers Integration

We exploit quantifier elimination in the global design of combined decision and semi-decision procedures for theories over non-disjoint signatures, thus providing in particular extensions of Nelson-Oppen results.     

Quantifier elimination by dependency sequents

We consider the problem of existential quantifier elimination for Boolean CNF formulas. We present a new method for solving this problem called derivation of dependency-sequents (DDS). A dependency-sequent (D-sequent) is used to record that a set of variables is redundant under a partial assignment. We introduce the join operation that produces new D-sequents from existing ones. We show that DDS is compositional, i.e., if our input formula is a conjunction of independent formulas, DDS automatically recognizes and exploits this information. We introduce an algorithm based on DDS and present experimental results demonstrating its potential.     

Applying Quantifier Elimination to the Birkhoff Interpolation Problem

This paper is devoted to show how to use Computer Algebra and Quantifier Elimination to solve some particular instances of the Birkhoff Interpolation Problem. In particular, this problem is completely solved for degrees less than or equal to 3 and any number of nodes and several instances of degree 4 and 5 by computing all the incidence normal poised matrices with such characteristics. The used Computer Algebra and Quantifier Elimination includes manipulation of multivariate polynomials, computation of determinants of matrices with polynomial entries and the formal manipulation of univariate polynomial inequalities by using Sturm—Habicht sequences and the Sign Determination Scheme.     

Quantifier guided aggregation using OWA operators

We consider multicriteria aggregation problems where, rather than requiring all the criteria be satisfied, we need only satisfy some portion of the criteria. The proportion of the critera required is specified in terms of a linguistic quantifier such as most . We use a fuzzy set representation of these linguistic quantifiers to obtain decision functions in the form of OWA aggregations. A methodology is suggested for including importances associated with the individual criteria. A procedure for determining the measure of “orness” directly from the quantifier is suggested. We introduce an extension of the OWA operators which involves the use of triangular norms. © 1996 John Wiley & Sons, Inc.     

Simulation and Optimization by Quantifier Elimination

We present a highly optimized method for the elimination of linear variables from a Boolean combination of polynomial equations and inequalities. In contrast to the basic method described earlier, the practical applicability of the present method goes far beyond academic examples. The optimization is achieved by various strategies to prune superfluous branches in the elimination tree constructed by the method.The main application concerns the simulation of large technical networks of (electric, mechanical or hydraulic) components, whose characteristic curves are piecewise linear (or quadratic) in the variables to be eliminated. Typical goals are the computation of admissible ranges for certain variables and the detection of a malfunction of a network component. The algorithms are currently used in a commercial software system for industrial applications.Moreover, we extend the author's elimination method for parametric linear programming to the non-convex case by allowing arbitraryand–orcombinations of parametric linear inequalities as constraints. We present a new strategy for finding smaller elimination sets and thus smaller elimination trees for parametric linear programming. Some benchmark examples from thenetliblibrary oflpproblems show the significance of this strategy even for convex linear programming problems.     

带n-元存在量词的描述逻辑MSC推理

分析了描述逻辑非标准推理的重要性,特别分析了描述逻辑MSC(Most Specific Concept)推理的研究现状和存在的问题.针对目前描述逻辑MSC推理不能处理n-元存在量词的不足,研究了带n-元存在量词的描述逻辑εL(n)的MSC推理问题.提出了一种新的εL(n)一描述图,利用描述树和描述图给出了描述逻辑εL(n)的MSC近似推理算法,并利用εL(n)-描述树嵌套和εL(n)-描述树描述图同态证明了MSC近似推理算法的正确性.作为一个附带的结果,利用εL(n)-描述树描述图同态给出了εL(n)-的实例推理算法,也证明了实例推理算法的正确性.     

Regular model checking for LTL(MSO)

Regular model checking is a form of symbolic model checking for parameterized and infinite-state systems whose states can be represented as words of arbitrary length over a finite alphabet, in which regular sets of words are used to represent sets of states. We present LTL(MSO), a combination of the logics monadic second-order logic (MSO) and LTL as a natural logic for expressing the temporal properties to be verified in regular model checking. In other words, LTL(MSO) is a natural specification language for both the system and the property under consideration. LTL(MSO) is a two-dimensional modal logic, where MSO is used for specifying properties of system states and transitions, and LTL is used for specifying temporal properties. In addition, the first-order quantification in MSO can be used to express properties parameterized on a position or process. We give a technique for model checking LTL(MSO), which is adapted from the automata-theoretic approach: a formula is translated to a buchi regular transition system with a regular set of accepting states, and regular model checking techniques are used to search for models. We have implemented the technique, and show its application to a number of parameterized algorithms from the literature.