Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
Publications

Publications by HASLab

2016

Formalization of the Pumping Lemma for Context-Free Languages

Authors
Ramos, MarcusViniciusMidena; Queiroz, RuyJ.G.B.de; Moreira, Nelma; Almeida, JoseCarlosBacelar;

Publication
JOURNAL OF FORMALIZED REASONING

Abstract
Context-free languages are highly important in computer language processing technology as well as in formal language theory. The Pumping Lemma is a property that is valid for all context-free languages, and is used to show the existence of non context-free languages. This paper presents a formalization, using the Coq proof assistant, of the Pumping Lemma for context-free languages.

2016

On the Formalization of Some Results of Context-Free Language Theory

Authors
Midena Ramos, MVM; de Queiroz, RJGB; Moreira, N; Bacelar Almeida, JCB;

Publication
LOGIC, LANGUAGE, INFORMATION, AND COMPUTATION

Abstract
This work describes a formalization effort, using the Coq proof assistant, of fundamental results related to the classical theory of context-free grammars and languages. These include closure properties (union, concatenation and Kleene star), grammar simplification (elimination of useless symbols, inaccessible symbols, empty rules and unit rules), the existence of a Chomsky Normal Form for context-free grammars and the Pumping Lemma for context-free languages. The result is an important set of libraries covering the main results of context-free language theory, with more than 500 lemmas and theorems fully proved and checked. This is probably the most comprehensive formalization of the classical context-free language theory in the Coq proof assistant done to the present date, and includes the important result that is the formalization of the Pumping Lemma for context-free languages.

2016

Formal Verification of a Space System's User Interface With the IVY Workbench

Authors
Campos, JC; Sousa, M; Alves, MCB; Harrison, MD;

Publication
IEEE TRANSACTIONS ON HUMAN-MACHINE SYSTEMS

Abstract
This paper describes the application of the IVY workbench to the formal analysis of a user interface for a safety-critical aerospace system. The operation manual of the system was used as a requirement document, and this made it possible to build a reference model of the user interface, focusing on navigation between displays, the information provided by each display, and how they are interrelated. Usability-related property specification patterns were then used to derive relevant properties for verification. This paper discusses both the modeling strategy and the analytical results found using the IVY workbench. The purpose of the reference model is to provide a standard against which future versions of the interface may be assessed.

2016

Validating an Approach to Formalize Use Cases with Ontologies

Authors
Couto, R; Ribeiro, AN; Campos, JC;

Publication
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE

Abstract
Use case driven development methodologies put use cases at the center of the software development process. However, in order to support automated development and analysis, use cases need to be appropriately formalized. This will also help guarantee consistency between requirements specifications and developed solutions. Formal methods tend to suffer from take up issues, as they are usually hard to accept by industry. In this context, it is relevant not only to produce languages and approaches to support formalization, but also to perform their validation. In previous works we have developed an approach to formalize use cases resorting to ontologies. In this paper we present the validation of one such approach. Through a three stage study, we evaluate the acceptance of the language and supporting tool. The first stage focusses on the acceptance of the process and language, the second on the support the tool provides to the process, and finally the third one on the tool's usability aspects. Results show test subjects found the approach feasible and useful and the tool easy to use.

2016

Templates as heuristics for proving properties of medical devices

Authors
Harrison, MD; Campos, JC; Masci, P; Curzon, P;

Publication
EAI Endorsed Trans. Creative Technologies

Abstract
This paper briefly describes how property templates have been used to analyse and explore the interactive behaviour of a specific medical device (an IV infusion pump). It is proposed that interactive devices that satisfy properties based on the templates are easier and safer to use. The property templates act as heuristics for the development of suitable properties tailored to the details of the particular device. A mathematically based approach is used to prove that a specification of the device satisfies the properties. Copyright © 2015 ICST.

2016

Modelling information resources and their salience in medical device design

Authors
Harrison, MD; Campos, JC; Ruksenas, R; Curzon, P;

Publication
EICS'16: PROCEEDINGS OF THE 8TH ACM SIGCHI SYMPOSIUM ON ENGINEERING INTERACTIVE COMPUTING SYSTEMS

Abstract
The paper describes a model that includes an explicit description of the information resources that are assumed to guide use, enabling a focus on properties of "plausible interactions". The information resources supported by an interactive system should be designed to encourage the correct use of the system. These resources signpost a user's interaction, helping to achieve desired goals. Analysing assumptions about information resource support is particularly relevant when a system is safety critical that is when interaction failure consequences could be dangerous, or walk-up-and-use where interaction failure may lead to reluctance to use with expensive consequences. The paper shows that expressing these resource constraints still provides a wider set of behaviours than would occur in practice. A resource may be more or less salient at a particular stage of the interaction and as a result potentially overlooked. For example, the resource may be accessible but not used because it does not seem relevant to the current goal. The paper describes how the resource framework can be augmented with additional information about the salience of the assumed resources. A medical device that is in common use in many hospitals is used as illustration.

  • 121
  • 261