Source author record

Achille Frigeri

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Logic in Computer Science math.CO Formal Languages and Automata Theory math.RA Software Engineering

Catalog footprint

Research overview

6works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Composing short 3-compressing words on a 2 letter alphabet

A finite deterministic (semi)automaton $\mathcal{A} =(Q,Σ,δ)$ is $k$ -compressible if there is some word $w\in Σ^+$ such that the image of its state set $Q$ under the natural action of $w$ is reduced by at least $k$ states. Such word, if it exists, is called a $k$ -compressing word for $\mathcal{A}$ . A word is $k$ -collapsing if it is $k$ -compressing for each $k$ -compressible automaton. We compute a set $W$ of short words such that each $3$ -compressible automata on a two letter alphabet is $3$ -compressed at least by a word in $W$ . Then we construct a shortest common superstring of the words in $W$ and, with a further refinement, we obtain a $3$ -collapsing word of length $53$ . Moreover, as previously announced, we show that the shortest $3$ -synchronizing word is not $3$ -collapsing, illustrating the new bounds $34\leq c(2,3)\leq 53$ for the length $c(2,3)$ of the shortest $3$ -collapsing word on a two letter alphabet.

preprint2014arXiv

Constraint LTL Satisfiability Checking without Automata

This paper introduces a novel technique to decide the satisfiability of formulae written in the language of Linear Temporal Logic with Both future and past operators and atomic formulae belonging to constraint system D (CLTLB(D) for short). The technique is based on the concept of bounded satisfiability, and hinges on an encoding of CLTLB(D) formulae into QF-EUD, the theory of quantifier-free equality and uninterpreted functions combined with D. Similarly to standard LTL, where bounded model-checking and SAT-solvers can be used as an alternative to automata-theoretic approaches to model-checking, our approach allows users to solve the satisfiability problem for CLTLB(D) formulae through SMT-solving techniques, rather than by checking the emptiness of the language of a suitable automaton A_ϕ. The technique is effective, and it has been implemented in our Zot formal verification tool.

preprint2012arXiv

Circular planar nearrings: geometrical and combinatorial aspects

Let $(N,Φ)$ be a circular Ferrero pair. We define the disk with center $b$ and radius $a$ , $\mathcal{D}(a;b)$ , as $\mathcal{D}(a;b)=\{x\in Φ(r)+c\mid r\neq 0,\ b\in Φ(r)+c,\ |(Φ(r)+c)\cap (Φ(a)+b)|=1\}.$ We prove that in the field-generated case there are many analogies with the Euclidean geometry. Moreover, if $\mathcal{B}^{\mathcal{D}}$ is the set of all disks, then, in some interesting cases, we show that the incidence structure $(N,\mathcal{B}^{\mathcal{D}},\in)$ is actually a balanced incomplete block design.

preprint2012arXiv

Fuzzy Time in LTL

In the last years, the adoption of active systems has increased in many fields of computer science, such as databases, sensor networks, and software engineering. These systems are able to automatically react to events, by collecting information from outside and internally generating new events. However, the collection of data is often hampered by uncertainty and vagueness that can arise from the imprecision of the monitoring infrastructure, unreliable data sources, and networks. The decision making mechanism used to produce a reaction is also imprecise, and cannot be evaluated in a crisp way. It depends on the evaluation of vague temporal constraints, which are expressed on the collected data by humans. Despite fuzzy logic has been mainly conceived as a mathematical abstraction to express vagueness, no attempt has been made to fuzzify the temporal modalities. Existing fuzzy languages do not allow us to represent temporal properties, such as "almost always" and "soon". Indeed, the semantics of existing fuzzy temporal operators is based on the idea of replacing classical connectives or propositions with their fuzzy counterparts. To overcome these limitations, we propose a temporal framework, FTL (Fuzzy-time Temporal Logic), to express vagueness on time. This framework formally defines a set of fuzzy temporal modalities, which can be customized by choosing a specific semantics for the connectives. The semantics of the language is sound, and the introduced modalities respect a set of expected mutual relations. We also prove that under the assumption that all events are crisp, FTL reduces to LTL. Finally, for some of the possible fuzzy interpretations of the connectives, we identify adequate sets of temporal operators, from which it is possible to derive all the others.

preprint2010arXiv

Bounded Reachability for Temporal Logic over Constraint Systems

We present CLTLB(D), an extension of PLTLB (PLTL with both past and future operators) augmented with atomic formulae built over a constraint system D. Even for decidable constraint systems, satisfiability and Model Checking problem of such logic can be undecidable. We introduce suitable restrictions and assumptions that are shown to make the satisfiability problem for the extended logic decidable. Moreover for a large class of constraint systems we propose an encoding that realize an effective decision procedure for the Bounded Reachability problem.

preprint2010arXiv

SMT-based Verification of LTL Specifications with Integer Constraints and its Application to Runtime Checking of Service Substitutability

An important problem that arises during the execution of service-based applications concerns the ability to determine whether a running service can be substituted with one with a different interface, for example if the former is no longer available. Standard Bounded Model Checking techniques can be used to perform this check, but they must be able to provide answers very quickly, lest the check hampers the operativeness of the application, instead of aiding it. The problem becomes even more complex when conversational services are considered, i.e., services that expose operations that have Input/Output data dependencies among them. In this paper we introduce a formal verification technique for an extension of Linear Temporal Logic that allows users to include in formulae constraints on integer variables. This technique applied to the substitutability problem for conversational services is shown to be considerably faster and with smaller memory footprint than existing ones.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.