| |
Records |
Links |
|
Author |
Intrigila, Benedetto; Salvo, Ivano; Sorgi, Stefano |
|
| |
Title |
A characterization of weakly Church-Rosser abstract reduction systems that are not Church-Rosser |
Type |
Journal Article |
| |
Year |
2001 |
Publication |
Information and Computation |
Abbreviated Journal |
|
|
| |
Volume |
171 |
Issue |
2 |
Pages |
137-155 |
|
| |
Keywords |
|
|
| |
Abstract |
Basic properties of rewriting systems can be stated in the framework of abstract reduction systems (ARS). Properties like confluence (or Church-Rosser, CR) and weak confluence (or weak Church-Rosser, WCR) and their relationships can be studied in this setting: as a matter of fact, well-known counterexamples to the implication WCR CR have been formulated as ARS. In this paper, starting from the observation that such counterexamples are structurally similar, we set out a graph-theoretic characterization of WCR ARS that is not CR in terms of a suitable class of reduction graphs, such that in every WCR not CR ARS, we can embed at least one element of this class. Moreover, we give a tighter characterization for a restricted class of ARS enjoying a suitable regularity condition. Finally, as a consequence of our approach, we prove some interesting results about ARS using the mathematical tools developed. In particular, we prove an extension of the Newman’s lemma and we find out conditions that, once assumed together with WCR property, ensure the unique normal form property. The Appendix treats two interesting examples, both generated by graph-rewriting rules, with specific combinatorial properties. |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Academic Press, Inc. |
Place of Publication  |
Duluth, MN, USA |
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0890-5401 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ Intrigila-Salvo-Sorgi:01 |
Serial |
68 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Tronci, Enrico |
|
| |
Title |
Automatic Synthesis of Control Software for an Industrial Automation Control System |
Type |
Conference Article |
| |
Year |
1999 |
Publication |
Proc.of: 14th IEEE International Conference on: Automated Software Engineering (ASE) |
Abbreviated Journal |
|
|
| |
Volume |
|
Issue |
|
Pages |
247-250 |
|
| |
Keywords |
|
|
| |
Abstract |
We present a case study on automatic synthesis of control software from formal specifications for an industrial automation control system. Our aim is to compare the effectiveness (i.e. design effort and controller quality) of automatic controller synthesis from closed loop formal specifications with that of manual controller design, followed by automatic verification. Our experimental results show that for industrial automation control systems, automatic synthesis is a viable and profitable (especially as far as design effort is concerned) alternative to manual design, followed by automatic verification. |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
|
Place of Publication |
Cocoa Beach, Florida, USA |
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
|
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ ase99 |
Serial |
49 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Böhm, Corrado; Tronci, Enrico |
|
| |
Title |
X-separability and left-invertibility in the λ-calculus (extended abstract, invited paper) |
Type |
Conference Article |
| |
Year |
1987 |
Publication |
Proceedings of: Temi e prospettive della Logica e della Filosofia della Scienza contemporanea |
Abbreviated Journal |
|
|
| |
Volume |
|
Issue |
|
Pages |
|
|
| |
Keywords |
|
|
| |
Abstract |
|
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
|
Place of Publication |
Cesena - Italy |
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
|
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ cesena87 |
Serial |
64 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Gribaudo, Marco; Horváth, Andras; Bobbio, Andrea; Tronci, Enrico; Ciancamerla, Ester; Minichino, Michele |
|
| |
Title |
Model-Checking Based on Fluid Petri Nets for the Temperature Control System of the ICARO Co-generative Plant |
Type |
Conference Article |
| |
Year |
2002 |
Publication |
21st International Conference on Computer Safety, Reliability and Security (SAFECOMP) |
Abbreviated Journal |
|
|
| |
Volume |
|
Issue |
|
Pages |
273-283 |
|
| |
Keywords |
|
|
| |
Abstract |
The modeling and analysis of hybrid systems is a recent and challenging research area which is actually dominated by two main lines: a functional analysis based on the description of the system in terms of discrete state (hybrid) automata (whose goal is to ascertain for conformity and reachability properties), and a stochastic analysis (whose aim is to provide performance and dependability measures). This paper investigates a unifying view between formal methods and stochastic methods by proposing an analysis methodology of hybrid systems based on Fluid Petri Nets (FPN). It is shown that the same FPN model can be fed to a functional analyser for model checking as well as to a stochastic analyser for performance evaluation. We illustrate our approach and show its usefulness by applying it to a “real world†hybrid system: the temperature control system of a co-generative plant. |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Springer |
Place of Publication |
Catania, Italy |
Editor |
Anderson, S.; Bologna, S.; Felici, M. |
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
Lecture Notes in Computer Science |
Abbreviated Series Title |
|
|
| |
Series Volume |
2434 |
Series Issue |
|
Edition |
|
|
| |
ISSN |
3-540-44157-3 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ safecomp02 |
Serial |
42 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Tronci, Enrico |
|
| |
Title |
Automatic Synthesis of Controllers from Formal Specifications |
Type |
Conference Article |
| |
Year |
1998 |
Publication |
Proc of 2nd IEEE International Conference on Formal Engineering Methods (ICFEM) |
Abbreviated Journal |
|
|
| |
Volume |
|
Issue |
|
Pages |
134-143 |
|
| |
Keywords |
|
|
| |
Abstract |
Many safety critical reactive systems are indeed embedded control systems. Usually a control system can be partitioned into two main subsystems: a controller and a plant. Roughly speaking: the controller observes the state of the plant and sends commands (stimulus) to the plant to achieve predefined goals. We show that when the plant can be modeled as a deterministic finite state system (FSS) it is possible to effectively use formal methods to automatically synthesize the program implementing the controller from the plant model and the given formal specifications for the closed loop system (plant+controller). This guarantees that the controller program is correct by construction. To the best of our knowledge there is no previously published effective algorithm to extract executable code for the controller from closed loop formal specifications. We show practical usefulness of our techniques by giving experimental results on their use to synthesize C programs implementing optimal controllers (OCs) for plants with more than 109 states. |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
|
Place of Publication |
Brisbane, Queensland, Australia |
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
|
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ icfem98 |
Serial |
52 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Fantechi, Alessandro; Gnesi, Stefania; Mazzanti, Franco; Pugliese, Rosario; Tronci, Enrico |
|
| |
Title |
A Symbolic Model Checker for ACTL |
Type |
Conference Article |
| |
Year |
1998 |
Publication |
International Workshop on Current Trends in Applied Formal Method (FM-Trends) |
Abbreviated Journal |
|
|
| |
Volume |
|
Issue |
|
Pages |
228-242 |
|
| |
Keywords |
|
|
| |
Abstract |
We present SAM, a symbolic model checker for ACTL, the action-based version of CTL. SAM relies on implicit representations of Labeled Transition Systems (LTSs), the semantic domain for ACTL formulae, and uses symbolic manipulation algorithms. SAM has been realized by translating (networks of) LTSs and, possibly recursive, ACTL formulae into BSP (Boolean Symbolic Programming), a programming language aiming at defining computations on boolean functions, and by using the BSP interpreter to carry out computations (i.e. verifications). |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Springer |
Place of Publication |
Boppard, Germany |
Editor |
Hutter, D.; Stephan, W.; Traverso, P.; Ullmann, M. |
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
Lecture Notes in Computer Science |
Abbreviated Series Title |
|
|
| |
Series Volume |
1641 |
Series Issue |
|
Edition |
|
|
| |
ISSN |
3-540-66462-9 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ fm-trends98 |
Serial |
51 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Della Penna, Giuseppe; Intrigila, Benedetto; Melatti, Igor; Tronci, Enrico; Venturini Zilli, Marisa |
|
| |
Title |
Finite horizon analysis of Markov Chains with the Mur$\varphi$ verifier |
Type |
Journal Article |
| |
Year |
2006 |
Publication |
Int. J. Softw. Tools Technol. Transf. |
Abbreviated Journal |
|
|
| |
Volume |
8 |
Issue |
4 |
Pages |
397-409 |
|
| |
Keywords |
|
|
| |
Abstract |
In this paper we present an explicit disk-based verification algorithm for Probabilistic Systems defining discrete time/finite state Markov Chains. Given a Markov Chain and an integer k (horizon), our algorithm checks whether the probability of reaching an error state in at most k steps is below a given threshold. We present an implementation of our algorithm within a suitable extension of the Mur$\varphi$ verifier. We call the resulting probabilistic model checker FHP-Mur$\varphi$ (Finite Horizon Probabilistic Mur$\varphi$). We present experimental results comparing FHP-Mur$\varphi$ with (a finite horizon subset of) PRISM, a state-of-the-art symbolic model checker for Markov Chains. Our experimental results show that FHP-Mur$\varphi$ can handle systems that are out of reach for PRISM, namely those involving arithmetic operations on the state variables (e.g. hybrid systems). |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Springer-Verlag |
Place of Publication |
Berlin, Heidelberg |
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
1433-2779 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ Dimtz06 |
Serial |
78 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Melatti, Igor; Palmer, Robert; Sawaya, Geoffrey; Yang, Yu; Kirby, Robert Mike; Gopalakrishnan, Ganesh |
|
| |
Title |
Parallel and distributed model checking in Eddy |
Type |
Journal Article |
| |
Year |
2009 |
Publication |
Int. J. Softw. Tools Technol. Transf. |
Abbreviated Journal |
|
|
| |
Volume |
11 |
Issue |
1 |
Pages |
13-25 |
|
| |
Keywords |
|
|
| |
Abstract |
Model checking of safety properties can be scaled up by pooling the CPU and memory resources of multiple computers. As compute clusters containing 100s of nodes, with each node realized using multi-core (e.g., 2) CPUs will be widespread, a model checker based on the parallel (shared memory) and distributed (message passing) paradigms will more efficiently use the hardware resources. Such a model checker can be designed by having each node employ two shared memory threads that run on the (typically) two CPUs of a node, with one thread responsible for state generation, and the other for efficient communication, including (1) performing overlapped asynchronous message passing, and (2) aggregating the states to be sent into larger chunks in order to improve communication network utilization. We present the design details of such a novel model checking architecture called Eddy. We describe the design rationale, details of how the threads interact and yield control, exchange messages, as well as detect termination. We have realized an instance of this architecture for the Murphi modeling language. Called Eddy_Murphi, we report its performance over the number of nodes as well as communication parameters such as those controlling state aggregation. Nearly linear reduction of compute time with increasing number of nodes is observed. Our thread task partition is done in such a way that it is modular, easy to port across different modeling languages, and easy to tune across a variety of platforms. |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Springer-Verlag |
Place of Publication |
Berlin, Heidelberg |
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
1433-2779 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ Mpsykg09 |
Serial |
80 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Della Penna, Giuseppe; Di Marco, Antinisca; Intrigila, Benedetto; Melatti, Igor; Pierantonio, Alfonso |
|
| |
Title |
Interoperability mapping from XML schemas to ER diagrams |
Type |
Journal Article |
| |
Year |
2006 |
Publication |
Data Knowl. Eng. |
Abbreviated Journal |
|
|
| |
Volume |
59 |
Issue |
1 |
Pages |
166-188 |
|
| |
Keywords |
|
|
| |
Abstract |
The eXtensible Markup Language (XML) is a de facto standard on the Internet and is now being used to exchange a variety of data structures. This leads to the problem of efficiently storing, querying and retrieving a great amount of data contained in XML documents. Unfortunately, XML data often need to coexist with historical data. At present, the best solution for storing XML into pre-existing data structures is to extract the information from the XML documents and adapt it to the data structures’ logical model (e.g., the relational model of a DBMS). In this paper, we introduce a technique called Xere (XML entity–relationship exchange) to assist the integration of XML data with other data sources. To this aim, we present an algorithm that maps XML schemas into entity–relationship diagrams, discuss its soundness and completeness and show its implementation in XSLT. |
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Elsevier Science Publishers B. V. |
Place of Publication |
Amsterdam, The Netherlands, The Netherlands |
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0169-023x |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ Ddimp06 |
Serial |
77 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Tronci, Enrico |
|
| |
Title |
Equational Programming in lambda-calculus |
Type |
Conference Article |
| |
Year |
1991 |
Publication |
Sixth Annual IEEE Symposium on Logic in Computer Science (LICS) |
Abbreviated Journal |
|
|
| |
Volume |
|
Issue |
|
Pages |
191-202 |
|
| |
Keywords |
|
|
| |
Abstract |
|
|
| |
Address |
|
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
IEEE Computer Society |
Place of Publication |
Amsterdam, The Netherlands |
Editor |
|
|
| |
Language |
|
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
|
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
|
Approved |
yes |
|
| |
Call Number |
Sapienza @ mari @ lics91 |
Serial |
58 |
|
| Permanent link to this record |
