PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials

This work presents a new framework for Gröbner-basis computations with Boolean polynomials. Boolean polynomials can be modelled in a rather simple way, with both coefficients and degree per variable lying in {0,1}$\{0,1\}$. The ring of Boolean polynomials is, however, not a polynomial ring, but rather the quotient ring of the polynomial ring over the field with two elements modulo the field equations x²=x$x^2=x$ for each variable x$x$. Therefore, the usual polynomial data structures seem not to be appropriate for fast Gröbner-basis computations. We introduce a specialised data structure for Boolean polynomials based on zero-suppressed binary decision diagrams (ZDDs), which are capable of handling these polynomials more efficiently with respect to memory consumption and also computational speed. Furthermore, we concentrate on high-level algorithmic aspects, taking into account the new data structures as well as structural properties of Boolean polynomials. For example, a new useless-pair criterion for Gröbner-basis computations in Boolean rings is introduced. One of the motivations for our work is the growing importance of formal hardware and software verification based on Boolean expressions, which suffer–besides from the complexity of the problems –from the lack of an adequate treatment of arithmetic components. We are convinced that algebraic methods are more suited and we believe that our preliminary implementation shows that Gröbner-bases on specific data structures can be capable of handling problems of industrial size.     

ReSpecT Nets: Towards an Analysis Methodology for ReSpecT Specifications

A key feature for infrastructures providing coordination services is the ability to define the behaviour of coordination abstractions according to the requirements identified at design-time. We take as a representative for this scenario the logic-based language ReSpecT (Reaction Specification Tuples), used to program the reactive behaviour of tuple centres. ReSpecT specifications are at the core of the engineering methodology underlying the TuCSoN infrastructure, and are therefore the “conceptual place” where formal methods can be fruitfully applied to guarantee relevant system properties.In this paper we introduce ReSpecT nets, a formalism that can be used to describe reactive behaviours that can succeed and fail, and that allows for an encoding to Petri nets with inhibitor arcs. ReSpecT nets are introduced to give a core model to a fragment of the ReSpecT language, and to pave the way for devising an analysis methodology including formal verification of safety and liveness properties. In particular, we provide a semantics to ReSpecT specifications through a mapping to ReSpecT nets. The potential of this approach for the analysis of ReSpecT specifications is discussed, presenting initial results for the analysis of safety properties.     

Robust filtering for uncertain linear systems: LMI based methods with parametric Lyapunov functions

This paper addresses the design of robust filters for linear continuous-time systems subject to parameter uncertainty in the state-space model. The uncertain parameters are supposed to belong to a given convex bounded polyhedral domain. Two methods based on parameter-dependent Lyapunov functions are proposed for designing linear stationary asymptotically stable filters that assure asymptotic stability and a guaranteed performance, irrespective of the uncertain parameters. The proposed filter designs are given in terms of linear matrix inequalities which depend on a scalar parameter that should be searched for in order to optimize the filter performance.     

The ** Part of the Theory of Ground Term Algebra Modulo an AC Symbol is Undecidable

We show that the ** part of the equational theory modulo an AC symbol is undecidable. This solves the open problem 25 from the RTA list. We show that this result holds also for the equational theory modulo an ACI symbol.     

RacoonWW1.3: A Monte Carlo program for four-fermion production at ee colliders

We present the Monte Carlo generator RacoonWW that computes cross sections to all processes e⁺e⁻→4f and e⁺e⁻→4fγ and calculates the complete electroweak radiative corrections to e⁺e⁻→WW→4f in the electroweak Standard Model in double-pole approximation. The calculation of the tree-level processes e⁺e⁻→4f and e⁺e⁻→4fγ is based on the full matrix elements for massless (polarized) fermions. When calculating radiative corrections to e⁺e⁻→WW→4f, the complete virtual doubly-resonant electroweak corrections are included, i.e. the factorizable and non-factorizable virtual corrections in double-pole approximation, and the real corrections are based on the full matrix elements for e⁺e⁻→4fγ. The matching of soft and collinear singularities between virtual and real corrections is done alternatively in two different ways, namely by using a subtraction method or by applying phase-space slicing. Higher-order initial-state photon radiation and naive QCD corrections are taken into account. RacoonWW also provides anomalous triple gauge-boson couplings for all processes e⁺e⁻→4f and anomalous quartic gauge-boson couplings for all processes e⁺e⁻→4fγ.