Recently, temporal logics such as μ-calculus and Computational Tree Logic, CTL, augmented with graded modalities have received attention from the scientific community, both from a theoretical side and from an applicative perspective. In both these se

Recently, complexity issues related to the decidability of the μ-calculus, when the universal and existential quantifiers are augmented with graded modalities, have been investigated by Kupfermann, Sattler and Vardi ([19]). Graded modalities refer to the use of the universal and existential quantifiers with the added capability to express the concept of at least k or all but k, for a non-negative integer k. In this paper we study the Computational Tree Logic CTL, a branching time extension of classical modal logic, augmented with graded modalities and investigate the complexity issues with respect to the model-checking problem. We consider a system model represented by a Kripke structure K and give an algorithm to solve the model-checking problem running in time O(|K| · |φ|) which is hence tight for the problem (here |φ| is the number of temporal and boolean operators and does not include the values occurring in the graded modalities). In this framework, the graded modalities express the ability to generate a user-defined number of counterexamples to a specification φ given in CTL. However, these multiple counterexamples can partially overlap, that is they may share some behavior. We have hence investigated the case when all of them are completely disjoint. In this case we prove that the model-checking problem is both NP-hard and coNP-hard and give an algorithm for solving it running in polynomial space. We have thus studied a fragment of graded-CTL, and have proved that the model-checking problem is solvable in polynomial time.

We are given a line of n identical processors (finite automata) that work synchronously. Each processor can transmit just one bit of information to the adjacent processors (if any) to the left and to the right. The computation starts at time 1 with the leftmost processor in an initial state and all other processors in a quiescent state. Given the time f(n), the problem is to set (synchronize) all the processors in a particular state for the first time, at the very same instant f(n). This problem is also known as the Firing Squad Synchronization Problem and was introduced by Moore in 1964. Mazoyer has given a minimal time solution with the least number of different states (six) and very recently he has given a minimal time solution for the constrained problem in which adjacent processors can exchange only one bit. In this paper we present solutions that synchronize the line at a given time, expressed as a function of n. In particular we give solutions that synchronize at the times nlogn, n√n, n 2 and 2 n . Moreover we also show how to compose solutions in such a way to obtain synchronizing solutions for all times expressed by polynomials with nonnegative coefficients. Clearly all such solutions work also in the general case when the bit constraint is relaxed.

We study the parallel word substitution operation: in a text t, all non overlapping occurrences of a word ω are simultaneously substituted in each possible decomposition of t with respect to ω. We give necessary conditions on the reversibility of t under parallel word substitution.

This paper presents the architecture and some tools of the software development workbench WSDW. The authors propose a structure-oriented workbench, in which interactive software tools are integrated through sharing a unique high level program representation, satisfying the request of independence from the source language. The data structure representing programs, the web structure, is based upon the mathematical concept of relation and it is easily implemented as a Prolog data base. Program transformations, given as web transformations, can be expressed as rewriting rules, so that software tools can be implemented as sets of rewriting rules and then added to the WSDW.>

The authors introduce web structures and their transformations and develop their theory in the framework of category theory. Once a program has been represented as a web structure, software tools, such as a high-level data flow analyzer or other general program transformers, can be written as sets of web structure production rules. An implementation of web structure transformations is in progress. The mathematical theory of web structure transformations allows form proofs of properties both at the metatheoretical and theoretical levels.>