Higher-Order Concurrency: Expressiveness and Decidability Results

Higher-order process calculi are formalisms for concurrency in which processes can be passed around in communications. Higher-order (or process-passing) concurrency is often presented as an alternative paradigm to the first order (or name-passing) concurrency of the pi-calculus for the description of mobile systems. These calculi are inspired by, and formally close to, the lambda-calculus, whose basic computational step ---beta-reduction--- involves term instantiation. The theory of higher-order process calculi is more complex than that of first-order process calculi. This shows up in, for instance, the definition of behavioral equivalences. A long-standing approach to overcome this burden is to define encodings of higher-order processes into a first-order setting, so as to transfer the theory of the first-order paradigm to the higher-order one. While satisfactory in the case of calculi with basic (higher-order) primitives, this indirect approach falls short in the case of higher-order process calculi featuring constructs for phenomena such as, e.g., localities and dynamic system reconfiguration, which are frequent in modern distributed systems. Indeed, for higher-order process calculi involving little more than traditional process communication, encodings into some first-order language are difficult to handle or do not exist. We then observe that foundational studies for higher-order process calculi must be carried out directly on them and exploit their peculiarities. This dissertation contributes to such foundational studies for higher-order process calculi. We concentrate on two closely interwoven issues in process calculi: expressiveness and decidability. Surprisingly, these issues have been little explored in the higher-order setting. Our research is centered around a core calculus for higher-order concurrency in which only the operators strictly necessary to obtain higher-order communication are retained. We develop the basic theory of this core calculus and rely on it to study the expressive power of issues universally accepted as basic in process calculi, namely synchrony, forwarding, and polyadic communication.

User interaction widgets for interactive theorem proving

Matita (that means pencil in Italian) is a new interactive theorem prover under development at the University of Bologna. When compared with state-of-the-art proof assistants, Matita presents both traditional and innovative aspects. The underlying calculus of the system, namely the Calculus of (Co)Inductive Constructions (CIC for short), is well-known and is used as the basis of another mainstream proof assistant—Coq—with which Matita is to some extent compatible. In the same spirit of several other systems, proof authoring is conducted by the user as a goal directed proof search, using a script for storing textual commands for the system. In the tradition of LCF, the proof language of Matita is procedural and relies on tactic and tacticals to proceed toward proof completion. The interaction paradigm offered to the user is based on the script management technique at the basis of the popularity of the Proof General generic interface for interactive theorem provers: while editing a script the user can move forth the execution point to deliver commands to the system, or back to retract (or “undo”) past commands. Matita has been developed from scratch in the past 8 years by several members of the Helm research group, this thesis author is one of such members. Matita is now a full-fledged proof assistant with a library of about 1.000 concepts. Several innovative solutions spun-off from this development effort. This thesis is about the design and implementation of some of those solutions, in particular those relevant for the topic of user interaction with theorem provers, and of which this thesis author was a major contributor. Joint work with other members of the research group is pointed out where needed. The main topics discussed in this thesis are briefly summarized below. Disambiguation. Most activities connected with interactive proving require the user to input mathematical formulae. Being mathematical notation ambiguous, parsing formulae typeset as mathematicians like to write down on paper is a challenging task; a challenge neglected by several theorem provers which usually prefer to fix an unambiguous input syntax. Exploiting features of the underlying calculus, Matita offers an efficient disambiguation engine which permit to type formulae in the familiar mathematical notation. Step-by-step tacticals. Tacticals are higher-order constructs used in proof scripts to combine tactics together. With tacticals scripts can be made shorter, readable, and more resilient to changes. Unfortunately they are de facto incompatible with state-of-the-art user interfaces based on script management. Such interfaces indeed do not permit to position the execution point inside complex tacticals, thus introducing a trade-off between the usefulness of structuring scripts and a tedious big step execution behavior during script replaying. In Matita we break this trade-off with tinycals: an alternative to a subset of LCF tacticals which can be evaluated in a more fine-grained manner. Extensible yet meaningful notation. Proof assistant users often face the need of creating new mathematical notation in order to ease the use of new concepts. The framework used in Matita for dealing with extensible notation both accounts for high quality bidimensional rendering of formulae (with the expressivity of MathMLPresentation) and provides meaningful notation, where presentational fragments are kept synchronized with semantic representation of terms. Using our approach interoperability with other systems can be achieved at the content level, and direct manipulation of formulae acting on their rendered forms is possible too. Publish/subscribe hints. Automation plays an important role in interactive proving as users like to delegate tedious proving sub-tasks to decision procedures or external reasoners. Exploiting the Web-friendliness of Matita we experimented with a broker and a network of web services (called tutors) which can try independently to complete open sub-goals of a proof, currently being authored in Matita. The user receives hints from the tutors on how to complete sub-goals and can interactively or automatically apply them to the current proof. Another innovative aspect of Matita, only marginally touched by this thesis, is the embedded content-based search engine Whelp which is exploited to various ends, from automatic theorem proving to avoiding duplicate work for the user. We also discuss the (potential) reusability in other systems of the widgets presented in this thesis and how we envisage the evolution of user interfaces for interactive theorem provers in the Web 2.0 era.

Molecular architecture of fur binding to iron-induced and - repressed genes in Helicobacter pylori

The ferric uptake regulator protein Fur regulates iron-dependent gene expression in bacteria. In the human pathogen Helicobacter pylori, Fur has been shown to regulate iron-induced and iron-repressed genes. Herein we investigate the molecular mechanisms that control this differential iron-responsive Fur regulation. Hydroxyl radical footprinting showed that Fur has different binding architectures, which characterize distinct operator typologies. On operators recognized with higher affinity by holo-Fur, the protein binds to a continuous AT-rich stretch of about 20 bp, displaying an extended protection pattern. This is indicative of protein wrapping around the DNA helix. DNA binding interference assays with the minor groove binding drug distamycin A, point out that the recognition of the holo-operators occurs through the minor groove of the DNA. By contrast, on the apo-operators, Fur binds primarily to thymine dimers within a newly identified TCATTn10TT consensus element, indicative of Fur binding to one side of the DNA, in the major groove of the double helix. Reconstitution of the TCATTn10TT motif within a holo-operator results in a feature binding swap from an holo-Fur- to an apo-Fur-recognized operator, affecting both affinity and binding architecture of Fur, and conferring apo-Fur repression features in vivo. Size exclusion chromatography indicated that Fur is a dimer in solution. However, in the presence of divalent metal ions the protein is able to multimerize. Accordingly, apo-Fur binds DNA as a dimer in gel shift assays, while in presence of iron, higher order complexes are formed. Stoichiometric Ferguson analysis indicates that these complexes correspond to one or two Fur tetramers, each bound to an operator element. Together these data suggest that the apo- and holo-Fur repression mechanisms apparently rely on two distinctive modes of operator-recognition, involving respectively the readout of a specific nucleotide consensus motif in the major groove for apo-operators, and the recognition of AT-rich stretches in the minor groove for holo-operators, whereas the iron-responsive binding affinity is controlled through metal-dependent shaping of the protein structure in order to match preferentially the major or the minor groove.

Social learning and action understanding in human observers: contributions of sensori-motor constraints and prior information

The aim of this thesis was to investigate the respective contribution of prior information and sensorimotor constraints to action understanding, and to estimate their consequences on the evolution of human social learning. Even though a huge amount of literature is dedicated to the study of action understanding and its role in social learning, these issues are still largely debated. Here, I critically describe two main perspectives. The first perspective interprets faithful social learning as an outcome of a fine-grained representation of others’ actions and intentions that requires sophisticated socio-cognitive skills. In contrast, the second perspective highlights the role of simpler decision heuristics, the recruitment of which is determined by individual and ecological constraints. The present thesis aims to show, through four experimental works, that these two contributions are not mutually exclusive. A first study investigates the role of the inferior frontal cortex (IFC), the anterior intraparietal area (AIP) and the primary somatosensory cortex (S1) in the recognition of other people’s actions, using a transcranial magnetic stimulation adaptation paradigm (TMSA). The second work studies whether, and how, higher-order and lower-order prior information (acquired from the probabilistic sampling of past events vs. derived from an estimation of biomechanical constraints of observed actions) interacts during the prediction of other people’s intentions. Using a single-pulse TMS procedure, the third study investigates whether the interaction between these two classes of priors modulates the motor system activity. The fourth study tests the extent to which behavioral and ecological constraints influence the emergence of faithful social learning strategies at a population level. The collected data contribute to elucidate how higher-order and lower-order prior expectations interact during action prediction, and clarify the neural mechanisms underlying such interaction. Finally, these works provide/open promising perspectives for a better understanding of social learning, with possible extensions to animal models.

Trait emotional intelligence: Evidence from italian adolescents and adults

Emotional intelligence (EI) represents an attribute of contemporary attractiveness for the scientific psychology community. Of particular interest for the present thesis are the conundrum related to the representation of this construct conceptualized as a trait (i.e., trait EI), which are in turn reflected in the current lack of agreement upon its constituent elements, posing significant challenges to research and clinical progress. Trait EI is defined as an umbrella personality-alike construct reflecting emotion-related dispositions and self-perceptions. The Trait Emotional Intelligence Questionnaire (TEIQue) was chosen as main measure, given its strong theoretical and psychometrical basis, including superior predictive validity when compared to other trait EI measures. Studies 1 and 2 aimed at validating the Italian 153-items forms of the TEIQue devoted to adolescents and adults. Analyses were done to investigate the structure of the questionnaire, its internal consistencies and gender differences at the facets, factor, and global level of both versions. Despite some low reliabilities, results from Studies 1 and 2 confirm the four-factor structure of the TEIQue. Study 3 investigated the utility of trait EI in a sample of adolescents over internalizing conditions (i.e., symptoms of anxiety and depression) and academic performance (grades at math and Italian language/literacy). Beyond trait EI, concurrent effects of demographic variables, higher order personality dimensions and non-verbal cognitive ability were controlled for. Study 4a and Study 4b addressed analogue research questions, through a meta-analysis and new data in on adults. In the latter case, effects of demographics, emotion regulation strategies, and the Big Five were controlled. Overall, these studies showed the incremental utility of the TEIQue in different domains beyond relevant predictors. Analyses performed at the level of the four-TEIQue factors consistently indicated that its predictive effects were mainly due to the factor Well-Being. Findings are discussed with reference to potential implication for theory and practice.