The Stable Revivals Model in CSP-Prover

The stable revivals model provides a new semantic framework for the process algebra Csp. The model has recently been added to the realm of established Csp models. Within the Csp context, it enhances the analysis of systems with regards to properties such as responsiveness and stuckness. These properties are essential in component based system design. In this paper we report on the implementation of different variants of the model within Csp-Prover. Based on Isabelle/HOL, Csp-Prover is an interactive proof tool for Csp refinement, which is generic in the underlying Csp model. On the practical side, our encoding of the model provides semi-automatic proof support for reasoning on responsiveness and stuckness. On the theoretical side, our implementation also yields a machine verification of the model 's soundness as well as of its expected properties.     

Reconstruction of a word from a multiset of its factors

Let be the multiset containing all factors of w of length k including repetitions. One of the main results is that if for all , then w=v. The bound is optimal; however we will also show that if for all , then w and v are structurally similar.     

Polyomino coloring and complex numbers

Usually polyominoes are represented as subsets of the lattice . In this paper we study a representation of polyominoes by Gaussian integers. Polyomino is represented by the set

Then we consider functions of type from the set of all polyominoes to an abelian group G, given by , where v is prime in (N(v) is the norm of v). Using the arithmetic of the ring we find necessary and sufficient conditions for such a function to be a coloring map.     

Structural properties of oracle classes

Denote by the class of oracles relative to which (collapsing oracles), and by the class of oracles relative to which (separating oracles). We present structural results on and . Using a diagonalization argument, we show that neither nor is closed under disjoint union, also known as join. We show that this implies that neither nor is closed under union, intersection, or symmetric difference. Consequently , the first level of the extended low hierarchy, is not closed under join.     

The Kolmogorov Expression Complexity of Logics

The purpose of the paper is to propose a completely new notion of complexity of logics in finite-model theory. It is the Kolmogorov variant of the Vardi'sexpression complexity. We define it by considering the value of the Kolmogorov complexityC(L[]) of the infinite stringL[] of all truth values of sentences ofLin . The higher is this value, the more expressive is the logicLin . If is a class of finite models, then the value ofC(L[]) over all ∈ is a measure of expressive power ofLin . Unboundedness ofC(L[])−C(L′[]) for ∈ implies nonexistence of a recursive interpretation ofLinL′. A version of this statement with complexities modulo oracles implies the nonexistence of any interpretation ofLinL′. Thus the valuesC(L[]) modulo oracles constitute an invariant of the expressive power of logics over finite models, depending on their real (absolute) expressive power, and not on the syntax. We investigate our notion for fragments of the infinitary logic ^ω_∞ω: least fixed point logic (LFP) and partial fixed point logic (PFP). We prove a precise characterization of 0–1 laws for these logics in terms of a certain boundedness condition placed onC(L[]). We get an extension of the notion of a 0–1 law by imposing an upper bound on the value ofC(L[]) growing not too fast with cardinality of , which still implies inexpressibility results similar to those implied by 0–1 laws. We also discuss classes in whichC(PFP^k[]) is very high. It appears that then PFP or its simple extension can define all the PSPACE subsets of .     

Combining OWL ontologies using -Connections

The standardization of the Web Ontology Language (OWL) leaves (at least) two crucial issues for Web-based ontologies unsatisfactorily resolved, namely how to represent and reason with multiple distinct, but linked ontologies, and how to enable effective knowledge reuse and sharing on the Semantic Web.In this paper, we present a solution for these fundamental problems based on -Connections. We aim to use -Connections to provide modelers with suitable means for developing Web ontologies in a modular way and to provide an alternative to the owl:imports construct.With such motivation, we present in this paper a syntactic and semantic extension of the Web Ontology language that covers -Connections of OWL-DL ontologies. We show how to use such an extension as an alternative to the owl:imports construct in many modeling situations. We investigate different combinations of the logics , and for which it is possible to design and implement reasoning algorithms, well-suited for optimization.Finally, we provide support for -Connections in both an ontology editor, SWOOP, and an OWL reasoner, Pellet.     

On systems of word equations with simple loop sets

Consider the infinite system S of word equations

For each , let T_k be the subsystem of S given by i{k,k+1,k+2}. We prove two properties of the above system.

(1) Let k≥1. If φ is a solution of T_k such that primitive roots of are of equal length, as well as primitive roots of , then φ is a solution of the whole S.

(2) If n=1 then, for any k≥2, a solution φ of T_k is also a solution of S.

Rewrite-Based Decision Procedures

The rewrite-based approach to satisfiability modulo theories consists of using generic theorem-proving strategies for first-order logic with equality. If one can prove that an inference system generates finitely many clauses from the presentation of a theory and a finite set of ground unit clauses, then any fair strategy based on that system can be used as a -satisfiability procedure. In this paper, we introduce a set of sufficient conditions to generalize the entire framework of rewrite-based -satisfiability procedures to rewrite-based -decision procedures. These conditions, collectively termed subterm-inactivity, will allow us to obtain rewrite-based -decision procedures for several theories, namely those of equality with uninterpreted functions, arrays with or without extensionality and two of its extensions, finite sets with extensionality and recursive data structures.     

On global continuity of Coons mappings in patching CAD surfaces

We tessellate a closed surface bounding a solid into four-sided patches . Each patch is the image of the unit square by which is the composition of a 2D Coons mapping and a bivariate function coming from a trimmed surface. Here, we concentrate on the analysis of the global continuity of the mappings over the whole surface. While using Coons functions to generate the mappings , arc length parametrization ensures that the images of the functions match pointwise at surface joints independently of the blending functions. We will describe a reparametrization technique based on cubic Bézier whose goal is to keep the shape of the initial curves while achieving arc length parametrization. The required accuracy of length computation is shown in L^∞-norm in order not to deteriorate the accuracy of the cubic spline approximation. Practical results from simulated and real CAD data which come from IGES files are reported.     

Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

A k-bounded pseudo-Boolean function is a real-valued function on n{0,1} that can be expressed as a sum of functions depending on at most k input bits. The k-bounded functions play an important role in a number of areas including molecular biology, biophysics, and evolutionary computation. We consider the problem of finding the Fourier coefficients of k-bounded functions, or equivalently, finding the coefficients of multilinear polynomials on n{−1,1} of degree k or less. Given a k-bounded function f with m non-zero Fourier coefficients for constant k, we present a randomized algorithm to find the Fourier coefficients of f with high probability in function evaluations. The best known upper bound was , where λ(n,m) is between and n depending on m. Our bound improves the previous bound by a factor of . It is almost tight with respect to the lower bound . In the process, we also consider the problem of finding k-bounded hypergraphs with a certain type of queries under an oracle with one-sided error. The problem is of self interest and we give an optimal algorithm for the problem.     

First-principles study of ground-state properties and phase stability of vanadium nitrides

Using a series of density functional electronic structure total energy calculations, we have systematically studied the ground-state properties and phase stability of vanadium nitrides. Comparison of enthalpy of formation shows that V ₂N is equally stable (polymorphic) in , and Fe₂C phases within a few meV. Formation enthalpy of the various phases considered for perfect stoichiometric V N_1.0 shows that it has enhanced stability in hexagonal WC and NiAs structures in relation to NaCl-type δ-phase. The TiAs phase of VN has nearly same energy as NaCl structure. Comparison of energetics of -type , for x=0 and 0.3333 and of , for x=0, 0.0625, 0.125 and 0.25 shows that vacancies on the nitrogen sublattice lowers the formation enthalpy in relation to respective stoichiometric phases which is in agreement with experiments, as bulk vanadium nitrides are known to be generally non-stoichiometric. The calculated dilute heat of solution for the interstitial nitrogen is found to be in good agreement with experimental values and shows that nitrogen prefers to occupy the octahedral sites in bcc vanadium. The α^′-FeN and martensite structures, considered for the metastable phases of vanadium nitrides, have higher formation enthalpy in relation to equilibrium phases. Analysis of electronic density of states of V ₂N shows that the low energy , and Fe₂C phases are characterized by broad V 3d-N 2p and V 3d bonding bands. Density of states of VN shows that in the low energy WC and NiAs phases some of the antibonding states are made empty, leading to a minimum near the Fermi level. For and , density of states shows that vacancies on the nitrogen sublattice introduce additional filled states in the 3d band below Fermi level enabling enhanced bonding. Comparison between bulk moduli and atomic volumes for the various phases of vanadium nitrides shows that higher bulk moduli are dominated by increased V–N bonds combined with low atomic volumes.     

An iterative algorithm for solving a pair of matrix equations over generalized centro-symmetric matrices

A matrix is said to be a symmetric orthogonal matrix if . A matrix is said to be generalized centro-symmetric (generalized central anti-symmetric) with respect to P, if A=PAP (A=−PAP). The generalized centro-symmetric matrices have wide applications in information theory, linear estimate theory and numerical analysis. In this paper, we propose a new iterative algorithm to compute a generalized centro-symmetric solution of the linear matrix equations . We show, when the matrix equations are consistent over generalized centro-symmetric matrix Y, for any initial generalized centro-symmetric matrix Y₁, the sequence {Y_k} generated by the introduced algorithm converges to a generalized centro-symmetric solution of matrix equations . The least Frobenius norm generalized centro-symmetric solution can be derived when a special initial generalized centro-symmetric matrix is chosen. Furthermore, the optimal approximation generalized centro-symmetric solution to a given generalized centro-symmetric matrix can be derived. Several numerical examples are given to show the efficiency of the presented method.     

Invariance properties in the root sensitivity of time-delay systems with double imaginary roots

If is an eigenvalue of a time-delay system for the delay τ₀ then is also an eigenvalue for the delays τ_k?τ₀+k2π/ω, for any k∈Z. We investigate the sensitivity, periodicity and invariance properties of the root for the case that is a double eigenvalue for some τ_k. It turns out that under natural conditions (the condition that the root exhibits the completely regular splitting property if the delay is perturbed), the presence of a double imaginary root for some delay τ₀ implies that is a simple root for the other delays τ_k, k≠0. Moreover, we show how to characterize the root locus around . The entire local root locus picture can be completely determined from the square root splitting of the double root. We separate the general picture into two cases depending on the sign of a single scalar constant; the imaginary part of the first coefficient in the square root expansion of the double eigenvalue.     

Interfaces as functors, programs as coalgebras—A final coalgebra theorem in intensional type theory

In [P. Hancock, A. Setzer, Interactive programs in dependent type theory, in: P. Clote, H. Schwichtenberg (Eds.), Proc. 14th Annu. Conf. of EACSL, CSL’00, Fischbau, Germany, 21–26 August 2000, Vol. 1862, Springer, Berlin, 2000, pp. 317–331, URL citeseer.ist.psu.edu/article/hancock00interactive.html; P. Hancock, A. Setzer, Interactive programs and weakly final coalgebras in dependent type theory, in: L. Crosilla, P. Schuster (Eds.), From Sets and Types to Topology and Analysis. Towards Practicable Foundations for Constructive Mathematics, Oxford Logic Guides, Clarendon Press, 2005, URL www.cs.swan.ac.uk/csetzer/] Hancock and Setzer introduced rules to extend Martin-Löf's type theory in order to represent interactive programming. The rules essentially reflect the existence of weakly final coalgebras for a general form of polynomial functor. The standard rules of dependent type theory allow the definition of inductive types, which correspond to initial algebras. Coalgebraic types are not represented in a direct way. In this article we show the existence of final coalgebras in intensional type theory for these kind of functors, where we require uniqueness of identity proofs () for the set of states and the set of commands which determine the functor. We obtain the result by identifying programs which have essentially the same behaviour, viz. are bisimular. This proves the rules of Setzer and Hancock admissible in ordinary type theory, if we replace definitional equality by bisimulation. All proofs [M. Michelbrink, Verifications of final coalgebra theorem in: Interfaces as Functors, Programs as Coalgebras—A Final Coalgebra Theorem in Intensional Type Theory, 2005, URL www.cs.swan.ac.uk/csmichel/] are verified in the theorem prover agda [C. Coquand, Agda, Internet, URL www.cs.chalmers.se/catarina/agda/; K. Peterson, A programming system for type theory, Technical Report, S-412 96, Chalmers University of Technology, Göteborg, 1982], which is based on intensional Martin-Löf type theory.     

Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem

We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties of small dimension. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve an elliptic curve discrete logarithm problem defined over in heuristic asymptotic running time ; and an elliptic problem over or a genus 2 problem over in heuristic asymptotic running time .     

A 3.4713-approximation algorithm for the capacitated multicast tree routing problem

Given an underlying communication network represented as an edge-weighted graph G=(V,E), a source node sV, a set of destination nodes DV, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of , where ρ denotes the best known approximation ratio for the Steiner minimum tree problem. Since ρ is about 1.55 at the writing of the paper, the ratio achieved by our new algorithm is less than 3.4713. In comparison, the previously best ratio was .     

Positive periodic solutions of second-order nonlinear differential systems with two parameters

By employing the Deimling fixed point index theory, we consider a class of second-order nonlinear differential systems with two parameters . We show that there exist three nonempty subsets of : Γ, Δ₁ and Δ₂ such that and the system has at least two positive periodic solutions for (λ,μ)Δ₁, one positive periodic solution for (λ,μ)Γ and no positive periodic solutions for (λ,μ)Δ₂. Meanwhile, we find two straight lines L₁ and L₂ such that Γ lies between L₁ and L₂.     

Tracking control with prescribed transient behaviour for systems of known relative degree

Tracking of a reference signal (assumed bounded with essentially bounded derivative) is considered for multi-input, multi-output linear systems satisfying the following structural assumptions: (i) arbitrary—but known—relative degree, (ii) the “high-frequency gain” matrix is sign definite—but of unknown sign, (iii) exponentially stable zero dynamics. The first control objective is tracking, by the output y, with prescribed accuracy: given λ>0 (arbitrarily small), determine a feedback strategy which ensures that, for every reference signal r, the tracking error e=y-r is ultimately bounded by λ (that is, e(t)<λ for all t sufficiently large). The second objective is guaranteed output transient performance: the evolution of the tracking error should be contained in a prescribed performance funnel (determined by a function ). Both objectives are achieved by a filter in conjunction with a feedback function of the filter states, the tracking error and a gain parameter. The latter is generated via a feedback function of the tracking error and the funnel parameter . Moreover, the feedback system is robust to nonlinear perturbations bounded by some continuous function of the output. The feedback structure essentially exploits an intrinsic high-gain property of the system/filter interconnection by ensuring that, if (t,e(t)) approaches the funnel boundary, then the gain attains values sufficiently large to preclude boundary contact.     

On generalized middle-level problem

Let be the subgraph of the hypercube Q_n induced by levels between k and n-k, where n?2k+1 is odd. The well-known middle-level conjecture asserts that is Hamiltonian for all k?1. We study this problem in for fixed k. It is known that and are Hamiltonian for all odd n?3. In this paper we prove that also is Hamiltonian for all odd n?5, and we conjecture that is Hamiltonian for every k?0 and every odd n?2k+1.     

Periodically switched stability induces exponential stability of discrete-time linear switched systems in the sense of Markovian probabilities

The conjecture that periodically switched stability implies absolute asymptotic stability of random infinite products of a finite set of square matrices, has recently been disproved under the guise of the finiteness conjecture. In this paper, we show that this conjecture holds in terms of Markovian probabilities. More specifically, let S_k∈C^n×n,1≤k≤K, be arbitrarily given K matrices and , where n,K≥2. Then we study the exponential stability of the following discrete-time switched dynamics S: where can be an arbitrary switching sequence.For a probability row-vector and an irreducible Markov transition matrix with , we denote by the Markovian probability on corresponding to . By using symbolic dynamics and ergodic-theoretic approaches, we show that, if S possesses the periodically switched stability then, (i) it is exponentially stable -almost surely; (ii) the set of stable switching sequences has the same Hausdorff dimension as . Thus, the periodically switched stability of a discrete-time linear switched dynamics implies that the system is exponentially stable for “almost” all switching sequences.