Recent Publications

Silva A, SergeyGoncharov, Milius S.  2014.  Towards a Coalgebraic Chomsky Hierarchy. IFIP International Conference on Theoretical Computer Science (IFIP TCS). 8705 Abstract1401.5277v3.pdf

The Chomsky hierarchy plays a prominent role in the foundations of the theoretical computer science relating classes of formal languages of primary importance. In this paper we use recent developments on coalgebraic and monad-based semantics to obtain a generic notion of a T-automaton, where T is a monad, which allows the uniform study of various notions of machines (e.g. finite state machines, multi-stack machines, Turing machines, valence automata, weighted automata). We use the generalized powerset construction to define a generic (trace) semantics for T-automata, and we show by numerous examples that it correctly instantiates for the known classes of machines/languages captured by the Chomsky hierarchy. Moreover, our approach provides new generic techniques for proving expressivity bounds of various machine-based models.

Silva A, Oliveira N, Barbosa LS.  2014.  Quantitative Analysis of Reo- Based Service Coordination. SAC - 29th Symposium On Applied Computing. Abstractimcreoosb.pdf

Quality of Service analysis of composed software systems is an active research area, with the goal of evaluating and improving performance and resource allocation in serviceoriented applications, namely, in the glue code –coordination layer– of such systems. Stochastic Reo offers constructs for
service coordination and allows the specification of stochastic values for channels. But its state-of-the-art semantic models fail in several (important) ways. In this paper, we will see how Interactive Markov chains (IMC), proposed as astochastic compositional model of concurrency, can be effectively used to serve as a compositional semantic model for Stochastic Reo. Treating IMC as a direct semantic model, gives rise to more faithful models and has obvious efficiency advantages. Moreover, tool support that exists for IMC is made available, without significant effort, to verify and reason about the coordination layer modelled as Reo connectors.

Cunha A.  2014.  Bounded Model Checking of Temporal Formulas with Alloy. Lecture Note in Computer Science. 8477 Abstract1207.2746v2.pdf

Alloy is formal modeling language based on first-order relational logic, with no specific support for specifying reactive systems. We propose the usage of temporal logic to specify such systems, and show how bounded model checking can be performed with the Alloy Analyzer.

Cunha A, Anjorin A, Giese H, Hermann F, Rensink A, Schurrr A.  2014.  BenchmarX. EDBT/ ICDT Workshops. 1133 Abstractpaper-13.pdf

Bidirectional transformation (BX) is a very active area of research interest. There is not only a growing body of theory, but also a rich set of tools supporting BX. The problem now arises that there is no commonly agreed-upon suite of tests or benchmarks that shows either the conformance of tools to theory, or the performance of tools in particular BX scenarios. This paper sets out to improve the state of affairs in this respect, by proposing a template and a set of required criteria for benchmark descriptions, as well as guidelines for the artifacts that should be provided for each included test. As a proof of concept, the paper additionally provides a detailed description of one concrete benchmark.

Carvalho P, Oliveira N, Henriques PR.  2014.  Unfuzzying Fuzzy Parsing. 3rd Symposium on Languages, Applications and Technologies. 38:101–108.
Oliveira N, Barbosa LS.  2014.  A self-adaptation strategy for service-based architectures. VIII Brazilian Symposium on Software Components, Architectures and Reuse. 2:44–53.
Fonte D, Boas IV, Oliveira N, da Cruz DC, Gançarski AL, Henriques PR.  2014.  Partial Correctness and Continuous Integration in Computer Supported Education. {CSEDU} 2014 - Proceedings of the 6th International Conference on Computer Supported Education, Volume 2, Barcelona, Spain, 1-3 April, 2014. 2:205–212.
Abreu R, Passos SL, Rosseti R.  2014.  Sensitivity Analysis of Spectrum-based Fault Localisation for Multi-Agent Systems. Proceedings of the 25th International Workshop on Principles of Diagnosis (DX’14). Abstractdx14_thu_am_s1_paper4.pdf

Diagnosing unwanted behaviour in Multi-Agent Systems (MASs) is a crucial task to assure the correct operation of a system. A light-weight technique inspired by the software-engineeringoriented techniques, the we have coined Extended Spectrum-based Fault Localisation for Multi-Agent Systems (ESFL-MAS) can be used to shorten the diagnose cycle by reducing the testing effort. As the technique relies on minimal information about the system, its diagnostic accuracy is inherently limited. In this paper, we study the impact of different similarity coefficients that are applied to the system execution spectra as we try to assess the correct operation of an agentbased application. The studied coefficients are proposed in the literature and we study the impact of them on the accuracy of spectrum-based fault localisation applied to multi-agent systems. Our experimental evaluation shows that three out of 42 (Jaccard, Ochiai, and Sorensen-Dice) have the most effective and stable performance throughout the variation of the number of passed and failed events.

Abreu R, Cardoso N.  2014.  An Efficient Distributed Algorithm for Computing Minimal Hitting Sets. Proceedings of the 25th International Workshop on Principles of Diagnosis (DX’14). Abstract

Computing minimal hitting sets for a collection of sets is an important problem in many domains (e.g., Spectrum-based Fault Localization). Being an NP-Hard problem, exhaustive algorithms are usually prohibitive for real-world, often large, problems. In practice, the usage of heuristic based approaches trade-off completeness for time efficiency. An example of such heuristic approaches is S TACCATO, which was proposed in the context of reasoning-based fault localization. In this paper, we propose an efficient distributed algorithm, dubbed MHS2, that renders the sequential search algorithm S TACCATO suitable to distributed, Map-Reduce environments. The results show that MHS2 scales to larger systems (when compared to STACCATO), while entailing either marginal or small run time overhead.

Casal J, Cledou MG.  2014.  Understanding Students' Mobility Habits Towards the Implementation of an Adaptive Ubiquitous Platform. Proceedings of the International Conference on Information Systems and Design of Communication - ISDOC '14. :67–72. Abstractisdoc14.pdf

Adapting technological environments to users is a concern since Mark Weiser launched the concept of ubiquitous computing and, in order to do that, is necessary to understand users' characteristics. In this context, the purpose of this paper is to present a study about students' mobility habits within a university campus, having the intention of getting insights towards the best place to set an interactive public display and of predicting the main characteristics of the audience that will be present on that spot in forthcoming periods. Thus, the envisioned results of this work will allow the adaptation of the contents exhibited on the device to the audience. To perform the study, a set of logs of accesses to the university's Wi-Fi was used, data mining techniques were implemented and forecasting models were built, using the line of work suggested by the CRISP-DM methodology. As result, students profile were built based on past wireless accesses and on their scholar schedules, and three time series models were used (Holt-Winters, Seasonal Naive and Simple Exponential Smoothing) to predict the presence of students on the envisioned spot in future periods.

Cledou MG.  2014.  A Virtual Factory for Smart City Service Integration. Proceedings of the 8th International Conference on Theory and Practice of Electronic Governance. :536–539. Abstracticegov2014paper.pdf

In the last years, new technologies - referred as emerging information and communication technologies (EICTs), have appeared and are immersed in peoples’ lives assisting them and facilitating their daily activities. Taking advantage of the diffusion and infusion of these technologies, governments are using EICTs to deliver better public services to citizens. However, to address citizens’ demands and to provide customer oriented services governments face various types of challenges. The aim of this research work is to provide solutions to some of the challenges, in particular to the rapid development of electronic public services (EPS) and the service integration in the context of development of smart cities. Following the aim, we propose an approach, called Virtual Factory for Smart City Service Integration. The idea of the virtual factory is to provide a framework to automatically produce software based on a given set of specifications of a family of EPS taking advantage of similarities in the EPS business processes. The expected contributions of this research work is to produce a domain specific language (DSL) for service specification and supporting tools that based on the produced specifications, workflow techniques and ideas of software product lines (SPL) can automatically produce software applications for EPS that can be easily parameterized and completed.

Masci P, Zhang Y, Jones P, Curzon P, Thimbleby H.  2014.  Formal Verification of Medical Device User Interfaces Using PVS. Fundamental Approaches to Software Engineering. Lecture Notes in Computer Science (LNCS), vol 8411:200-214. Abstractmasci-fase2014.pdf

We present a formal verification approach for detecting design issues related to user interaction, with a focus on user interface of medical devices. The approach makes a novel use of configuration diagrams proposed by Rushby to formally verify important human factors properties of user interface implementation. In particular, it first translates the software implementation of user interface into an equivalent formal specification, from which a behavioral model is constructed using theorem proving; human factors properties are then verified against the behavioral model; lastly, a comprehensive set of test inputs are produced by exploring the behavioral model, which can be used to challenge the real interface implementation and to ensure that the issues detected in the behavior model do apply to the implementation. We have prototyped the approach based on the PVS proof system, and applied it to analyze the user interface of a real medical device. The analysis detected several interaction design issues in the device, which may potentially lead to severe consequences.

Masci P, Oladimeji P, Curzon P, Thimbleby H.  2014.  Using PVSio-web to demonstrate software issues in medical user interfaces. 4th International Symposium on Foundations of Healthcare Information Engineering and Systems (FHIES2014). Lecture Notes in Computer Science book series (LNCS), volume 9062 Abstractmasci-fhies14.pdf

We have used formal methods technology to investigate software and user interface design issues that may induce use error in medical devices. Our approach is based on mathematical models that capture safety concerns related to the use of a device. We analysed nine commercial medical devices from six manufacturers with our approach, and precisely identified 30 design issues. All identified issues can induce use errors that could lead to adverse clinical consequences, such as numbers being incorrectly entered. An issue with formal approaches is in making results accessible to developers, human factors experts and clinicians. In this paper, we use our tool PVSio-web to demonstrate the identified issues: PVSio-web allows us to generate realistic and interactive user interface prototypes from the same mathematical models used for analysis. Users can explore the behaviour of the prototypes by pressing buttons on realistic user interfaces that reproduce the functionality and visual representation of the real devices. Users can examine the device behaviour resulting from any interaction. Key sequences identified from analysis can be used to explore in detail the identified design issues in an accessible way.

Masci P, Zhang Y, Jones P, Thimbleby H, Curzon P.  2014.  A generic user interface architecture for analyzing use hazards in infusion pump software. Proceedings of Medical Cyber Physical Systems Workshop (MedCPS2014). Abstractmasci-medcps2014.pdf

This paper presents a generic infusion pump user interface (GIP-UI) architecture that intends to capture the common characteristics and functionalities of interactive software incorporated in broad classes of infusion pumps. It is designed to facilitate the identification of use hazards and their causes in infusion pump designs. This architecture constitutes our first e!ort at establishing a model-based risk analysis methodology that helps manufacturers identify and mitigate use hazards in their products at early stages of the development life-cycle. The applicability of the GIP-UI architecture has been confirmed in a hazard analysis focusing on the number entry software of existing infusion pumps, in which the GIP-UI architecture is used to identify a substantial set of user interface design errors that may contribute to use hazards found in infusion pump incidents.

Masci P, Zhang Y, Jones P, Oladimeji P, D'Urso E, Bernardeschi C, Curzon P, Thimbleby H.  2014.  Combining PVSio with Stateflow. Proceedings of the 6th NASA Formal Methods Symposium (NFM2014). Lecture Notes in Computer Science book series (LNCS, volume 8430) Abstractpvsioweb-stateflow-nfm2014.pdf

An approach to integrating PVS executable specifications and Stateflow models is presented that uses web services to enable a seamless exchange of simulation events and data between PVS and Stateflow. Thus, it allows the wide range of applications developed in Stateflow to benefit from the rigor of PVS verification. The effectiveness of the approach is demonstrated on a medical device prototype, which consists of a user interface developed in PVS and a software controller implemented in Stateflow. Simulation on the prototype shows that simulation data produced is exchanged smoothly between in PVSio and Stateflow.