Relatório de estágio de Qualificação Profissional

Mestrado em Educação Pré-Escolar

Framework development for providing accessibility to qualitative spatial calculi

Dissertation submitted in partial fulfillment of the requirements for the Degree of Master of Science in Geospatial Technologies.

A proof system for lock-free concurrency

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

A logical foundation for session-based concurrent computation

Linear logic has long been heralded for its potential of providing a logical basis for concurrency. While over the years many research attempts were made in this regard, a Curry-Howard correspondence between linear logic and concurrent computation was only found recently, bridging the proof theory of linear logic and session-typed process calculus. Building upon this work, we have developed a theory of intuitionistic linear logic as a logical foundation for session-based concurrent computation, exploring several concurrency related phenomena such as value-dependent session types and polymorphic sessions within our logical framework in an arguably clean and elegant way, establishing with relative ease strong typing guarantees due to the logical basis, which ensure the fundamental properties of type preservation and global progress, entailing the absence of deadlocks in communication. We develop a general purpose concurrent programming language based on the logical interpretation, combining functional programming with a concurrent, session-based process layer through the form of a contextual monad, preserving our strong typing guarantees of type preservation and deadlock-freedom in the presence of general recursion and higher-order process communication. We introduce a notion of linear logical relations for session typed concurrent processes, developing an arguably uniform technique for reasoning about sophisticated properties of session-based concurrent computation such as termination or equivalence based on our logical approach, further supporting our goal of establishing intuitionistic linear logic as a logical foundation for sessionbased concurrency.

Machine ethics via logic programming

Machine ethics is an interdisciplinary field of inquiry that emerges from the need of imbuing autonomous agents with the capacity of moral decision-making. While some approaches provide implementations in Logic Programming (LP) systems, they have not exploited LP-based reasoning features that appear essential for moral reasoning. This PhD thesis aims at investigating further the appropriateness of LP, notably a combination of LP-based reasoning features, including techniques available in LP systems, to machine ethics. Moral facets, as studied in moral philosophy and psychology, that are amenable to computational modeling are identified, and mapped to appropriate LP concepts for representing and reasoning about them. The main contributions of the thesis are twofold. First, novel approaches are proposed for employing tabling in contextual abduction and updating – individually and combined – plus a LP approach of counterfactual reasoning; the latter being implemented on top of the aforementioned combined abduction and updating technique with tabling. They are all important to model various issues of the aforementioned moral facets. Second, a variety of LP-based reasoning features are applied to model the identified moral facets, through moral examples taken off-the-shelf from the morality literature. These applications include: (1) Modeling moral permissibility according to the Doctrines of Double Effect (DDE) and Triple Effect (DTE), demonstrating deontological and utilitarian judgments via integrity constraints (in abduction) and preferences over abductive scenarios; (2) Modeling moral reasoning under uncertainty of actions, via abduction and probabilistic LP; (3) Modeling moral updating (that allows other – possibly overriding – moral rules to be adopted by an agent, on top of those it currently follows) via the integration of tabling in contextual abduction and updating; and (4) Modeling moral permissibility and its justification via counterfactuals, where counterfactuals are used for formulating DDE.

Comunicar a Direito

Relatório de estágio de mestrado em Ciências da Comunicação (área de especialização em Informação e Jornalismo)

A relação entre família e escola e a perspectiva de minimização das dificuldades comportamentais e cognitivas apresentadas por adolescentes com Síndrome do Alcoolismo Fetal (SAF): estudos de casos na cidade de Manaus

Dissertação de mestrado em Educação Especial (área de especialização em Dificuldades de Aprendizagem Específicas)

A Bayesian network approach to the database serch problem in criminal proceedings

Background The 'database search problem', that is, the strengthening of a case - in terms of probative value - against an individual who is found as a result of a database search, has been approached during the last two decades with substantial mathematical analyses, accompanied by lively debate and centrally opposing conclusions. This represents a challenging obstacle in teaching but also hinders a balanced and coherent discussion of the topic within the wider scientific and legal community. This paper revisits and tracks the associated mathematical analyses in terms of Bayesian networks. Their derivation and discussion for capturing probabilistic arguments that explain the database search problem are outlined in detail. The resulting Bayesian networks offer a distinct view on the main debated issues, along with further clarity. Methods As a general framework for representing and analyzing formal arguments in probabilistic reasoning about uncertain target propositions (that is, whether or not a given individual is the source of a crime stain), this paper relies on graphical probability models, in particular, Bayesian networks. This graphical probability modeling approach is used to capture, within a single model, a series of key variables, such as the number of individuals in a database, the size of the population of potential crime stain sources, and the rarity of the corresponding analytical characteristics in a relevant population. Results This paper demonstrates the feasibility of deriving Bayesian network structures for analyzing, representing, and tracking the database search problem. The output of the proposed models can be shown to agree with existing but exclusively formulaic approaches. Conclusions The proposed Bayesian networks allow one to capture and analyze the currently most well-supported but reputedly counter-intuitive and difficult solution to the database search problem in a way that goes beyond the traditional, purely formulaic expressions. The method's graphical environment, along with its computational and probabilistic architectures, represents a rich package that offers analysts and discussants with additional modes of interaction, concise representation, and coherent communication.

Suoraviivaisesti verkostoista

Kirjallisuusarvostelu

Scheduling of guarded command based models

Formal methods provide a means of reasoning about computer programs in order to prove correctness criteria. One subtype of formal methods is based on the weakest precondition predicate transformer semantics and uses guarded commands as the basic modelling construct. Examples of such formalisms are Action Systems and Event-B. Guarded commands can intuitively be understood as actions that may be triggered when an associated guard condition holds. Guarded commands whose guards hold are nondeterministically chosen for execution, but no further control flow is present by default. Such a modelling approach is convenient for proving correctness, and the Refinement Calculus allows for a stepwise development method. It also has a parallel interpretation facilitating development of concurrent software, and it is suitable for describing event-driven scenarios. However, for many application areas, the execution paradigm traditionally used comprises more explicit control flow, which constitutes an obstacle for using the above mentioned formal methods. In this thesis, we study how guarded command based modelling approaches can be conveniently and efficiently scheduled in different scenarios. We first focus on the modelling of trust for transactions in a social networking setting. Due to the event-based nature of the scenario, the use of guarded commands turns out to be relatively straightforward. We continue by studying modelling of concurrent software, with particular focus on compute-intensive scenarios. We go from theoretical considerations to the feasibility of implementation by evaluating the performance and scalability of executing a case study model in parallel using automatic scheduling performed by a dedicated scheduler. Finally, we propose a more explicit and non-centralised approach in which the flow of each task is controlled by a schedule of its own. The schedules are expressed in a dedicated scheduling language, and patterns assist the developer in proving correctness of the scheduled model with respect to the original one.

Formal development and quantitative verification of dependable systems

-

Spontaneous Focusing on Quantitative Relations and the Development of Rational Number Conceptual Knowledge

The aim of the present set of studies was to explore primary school children’s Spontaneous Focusing On quantitative Relations (SFOR) and its role in the development of rational number conceptual knowledge. The specific goals were to determine if it was possible to identify a spontaneous quantitative focusing tendency that indexes children’s tendency to recognize and utilize quantitative relations in non-explicitly mathematical situations and to determine if this tendency has an impact on the development of rational number conceptual knowledge in late primary school. To this end, we report on six original empirical studies that measure SFOR in children ages five to thirteen years and the development of rational number conceptual knowledge in ten- to thirteen-year-olds. SFOR measures were developed to determine if there are substantial differences in SFOR that are not explained by the ability to use quantitative relations. A measure of children’s conceptual knowledge of the magnitude representations of rational numbers and the density of rational numbers is utilized to capture the process of conceptual change with rational numbers in late primary school students. Finally, SFOR tendency was examined in relation to the development of rational number conceptual knowledge in these students. Study I concerned the first attempts to measure individual differences in children’s spontaneous recognition and use of quantitative relations in 86 Finnish children from the ages of five to seven years. Results revealed that there were substantial inter-individual differences in the spontaneous recognition and use of quantitative relations in these tasks. This was particularly true for the oldest group of participants, who were in grade one (roughly seven years old). However, the study did not control for ability to solve the tasks using quantitative relations, so it was not clear if these differences were due to ability or SFOR. Study II more deeply investigated the nature of the two tasks reported in Study I, through the use of a stimulated-recall procedure examining children’s verbalizations of how they interpreted the tasks. Results reveal that participants were able to verbalize reasoning about their quantitative relational responses, but not their responses based on exact number. Furthermore, participants’ non-mathematical responses revealed a variety of other aspects, beyond quantitative relations and exact number, which participants focused on in completing the tasks. These results suggest that exact number may be more easily perceived than quantitative relations. As well, these tasks were revealed to contain both mathematical and non-mathematical aspects which were interpreted by the participants as relevant. Study III investigated individual differences in SFOR 84 children, ages five to nine, from the US and is the first to report on the connection between SFOR and other mathematical abilities. The cross-sectional data revealed that there were individual differences in SFOR. Importantly, these differences were not entirely explained by the ability to solve the tasks using quantitative relations, suggesting that SFOR is partially independent from the ability to use quantitative relations. In other words, the lack of use of quantitative relations on the SFOR tasks was not solely due to participants being unable to solve the tasks using quantitative relations, but due to a lack of the spontaneous attention to the quantitative relations in the tasks. Furthermore, SFOR tendency was found to be related to arithmetic fluency among these participants. This is the first evidence to suggest that SFOR may be a partially distinct aspect of children’s existing mathematical competences. Study IV presented a follow-up study of the first graders who participated in Studies I and II, examining SFOR tendency as a predictor of their conceptual knowledge of fraction magnitudes in fourth grade. Results revealed that first graders’ SFOR tendency was a unique predictor of fraction conceptual knowledge in fourth grade, even after controlling for general mathematical skills. These results are the first to suggest that SFOR tendency may play a role in the development of rational number conceptual knowledge. Study V presents a longitudinal study of the development of 263 Finnish students’ rational number conceptual knowledge over a one year period. During this time participants completed a measure of conceptual knowledge of the magnitude representations and the density of rational numbers at three time points. First, a Latent Profile Analysis indicated that a four-class model, differentiating between those participants with high magnitude comparison and density knowledge, was the most appropriate. A Latent Transition Analysis reveal that few students display sustained conceptual change with density concepts, though conceptual change with magnitude representations is present in this group. Overall, this study indicated that there were severe deficiencies in conceptual knowledge of rational numbers, especially concepts of density. The longitudinal Study VI presented a synthesis of the previous studies in order to specifically detail the role of SFOR tendency in the development of rational number conceptual knowledge. Thus, the same participants from Study V completed a measure of SFOR, along with the rational number test, including a fourth time point. Results reveal that SFOR tendency was a predictor of rational number conceptual knowledge after two school years, even after taking into consideration prior rational number knowledge (through the use of residualized SFOR scores), arithmetic fluency, and non-verbal intelligence. Furthermore, those participants with higher-than-expected SFOR scores improved significantly more on magnitude representation and density concepts over the four time points. These results indicate that SFOR tendency is a strong predictor of rational number conceptual development in late primary school children. The results of the six studies reveal that within children’s existing mathematical competences there can be identified a spontaneous quantitative focusing tendency named spontaneous focusing on quantitative relations. Furthermore, this tendency is found to play a role in the development of rational number conceptual knowledge in primary school children. Results suggest that conceptual change with the magnitude representations and density of rational numbers is rare among this group of students. However, those children who are more likely to notice and use quantitative relations in situations that are not explicitly mathematical seem to have an advantage in the development of rational number conceptual knowledge. It may be that these students gain quantitative more and qualitatively better self-initiated deliberate practice with quantitative relations in everyday situations due to an increased SFOR tendency. This suggests that it may be important to promote this type of mathematical activity in teaching rational numbers. Furthermore, these results suggest that there may be a series of spontaneous quantitative focusing tendencies that have an impact on mathematical development throughout the learning trajectory.

Formal development of resilient distributed systems

Resilience is the property of a system to remain trustworthy despite changes. Changes of a different nature, whether due to failures of system components or varying operational conditions, significantly increase the complexity of system development. Therefore, advanced development technologies are required to build robust and flexible system architectures capable of adapting to such changes. Moreover, powerful quantitative techniques are needed to assess the impact of these changes on various system characteristics. Architectural flexibility is achieved by embedding into the system design the mechanisms for identifying changes and reacting on them. Hence a resilient system should have both advanced monitoring and error detection capabilities to recognise changes as well as sophisticated reconfiguration mechanisms to adapt to them. The aim of such reconfiguration is to ensure that the system stays operational, i.e., remains capable of achieving its goals. Design, verification and assessment of the system reconfiguration mechanisms is a challenging and error prone engineering task. In this thesis, we propose and validate a formal framework for development and assessment of resilient systems. Such a framework provides us with the means to specify and verify complex component interactions, model their cooperative behaviour in achieving system goals, and analyse the chosen reconfiguration strategies. Due to the variety of properties to be analysed, such a framework should have an integrated nature. To ensure the system functional correctness, it should rely on formal modelling and verification, while, to assess the impact of changes on such properties as performance and reliability, it should be combined with quantitative analysis. To ensure scalability of the proposed framework, we choose Event-B as the basis for reasoning about functional correctness. Event-B is a statebased formal approach that promotes the correct-by-construction development paradigm and formal verification by theorem proving. Event-B has a mature industrial-strength tool support { the Rodin platform. Proof-based verification as well as the reliance on abstraction and decomposition adopted in Event-B provides the designers with a powerful support for the development of complex systems. Moreover, the top-down system development by refinement allows the developers to explicitly express and verify critical system-level properties. Besides ensuring functional correctness, to achieve resilience we also need to analyse a number of non-functional characteristics, such as reliability and performance. Therefore, in this thesis we also demonstrate how formal development in Event-B can be combined with quantitative analysis. Namely, we experiment with integration of such techniques as probabilistic model checking in PRISM and discrete-event simulation in SimPy with formal development in Event-B. Such an integration allows us to assess how changes and di erent recon guration strategies a ect the overall system resilience. The approach proposed in this thesis is validated by a number of case studies from such areas as robotics, space, healthcare and cloud domain.

Formal modelling for digital media distribution

Human beings have always strived to preserve their memories and spread their ideas. In the beginning this was always done through human interpretations, such as telling stories and creating sculptures. Later, technological progress made it possible to create a recording of a phenomenon; first as an analogue recording onto a physical object, and later digitally, as a sequence of bits to be interpreted by a computer. By the end of the 20th century technological advances had made it feasible to distribute media content over a computer network instead of on physical objects, thus enabling the concept of digital media distribution. Many digital media distribution systems already exist, and their continued, and in many cases increasing, usage is an indicator for the high interest in their future enhancements and enriching. By looking at these digital media distribution systems, we have identified three main areas of possible improvement: network structure and coordination, transport of content over the network, and the encoding used for the content. In this thesis, our aim is to show that improvements in performance, efficiency and availability can be done in conjunction with improvements in software quality and reliability through the use of formal methods: mathematical approaches to reasoning about software so that we can prove its correctness, together with the desirable properties. We envision a complete media distribution system based on a distributed architecture, such as peer-to-peer networking, in which different parts of the system have been formally modelled and verified. Starting with the network itself, we show how it can be formally constructed and modularised in the Event-B formalism, such that we can separate the modelling of one node from the modelling of the network itself. We also show how the piece selection algorithm in the BitTorrent peer-to-peer transfer protocol can be adapted for on-demand media streaming, and how this can be modelled in Event-B. Furthermore, we show how modelling one peer in Event-B can give results similar to simulating an entire network of peers. Going further, we introduce a formal specification language for content transfer algorithms, and show that having such a language can make these algorithms easier to understand. We also show how generating Event-B code from this language can result in less complexity compared to creating the models from written specifications. We also consider the decoding part of a media distribution system by showing how video decoding can be done in parallel. This is based on formally defined dependencies between frames and blocks in a video sequence; we have shown that also this step can be performed in a way that is mathematically proven correct. Our modelling and proving in this thesis is, in its majority, tool-based. This provides a demonstration of the advance of formal methods as well as their increased reliability, and thus, advocates for their more wide-spread usage in the future.

An Interactive Theorem Prover for First-Order Dynamic Logic

Dynamic logic is an extension of modal logic originally intended for reasoning about computer programs. The method of proving correctness of properties of a computer program using the well-known Hoare Logic can be implemented by utilizing the robustness of dynamic logic. For a very broad range of languages and applications in program veri cation, a theorem prover named KIV (Karlsruhe Interactive Veri er) Theorem Prover has already been developed. But a high degree of automation and its complexity make it di cult to use it for educational purposes. My research work is motivated towards the design and implementation of a similar interactive theorem prover with educational use as its main design criteria. As the key purpose of this system is to serve as an educational tool, it is a self-explanatory system that explains every step of creating a derivation, i.e., proving a theorem. This deductive system is implemented in the platform-independent programming language Java. In addition, a very popular combination of a lexical analyzer generator, JFlex, and the parser generator BYacc/J for parsing formulas and programs has been used.