Constraint handling rules. Compositional semantics and program transformation

This thesis intends to investigate two aspects of Constraint Handling Rules (CHR). It proposes a compositional semantics and a technique for program transformation. CHR is a concurrent committed-choice constraint logic programming language consisting of guarded rules, which transform multi-sets of atomic formulas (constraints) into simpler ones until exhaustion [Frü06] and it belongs to the declarative languages family. It was initially designed for writing constraint solvers but it has recently also proven to be a general purpose language, being as it is Turing equivalent [SSD05a]. Compositionality is the first CHR aspect to be considered. A trace based compositional semantics for CHR was previously defined in [DGM05]. The reference operational semantics for such a compositional model was the original operational semantics for CHR which, due to the propagation rule, admits trivial non-termination. In this thesis we extend the work of [DGM05] by introducing a more refined trace based compositional semantics which also includes the history. The use of history is a well-known technique in CHR which permits us to trace the application of propagation rules and consequently it permits trivial non-termination avoidance [Abd97, DSGdlBH04]. Naturally, the reference operational semantics, of our new compositional one, uses history to avoid trivial non-termination too. Program transformation is the second CHR aspect to be considered, with particular regard to the unfolding technique. Said technique is an appealing approach which allows us to optimize a given program and in more detail to improve run-time efficiency or spaceconsumption. Essentially it consists of a sequence of syntactic program manipulations which preserve a kind of semantic equivalence called qualified answer [Frü98], between the original program and the transformed ones. The unfolding technique is one of the basic operations which is used by most program transformation systems. It consists in the replacement of a procedure-call by its definition. In CHR every conjunction of constraints can be considered as a procedure-call, every CHR rule can be considered as a procedure and the body of said rule represents the definition of the call. While there is a large body of literature on transformation and unfolding of sequential programs, very few papers have addressed this issue for concurrent languages. We define an unfolding rule, show its correctness and discuss some conditions in which it can be used to delete an unfolded rule while preserving the meaning of the original program. Finally, confluence and termination maintenance between the original and transformed programs are shown. This thesis is organized in the following manner. Chapter 1 gives some general notion about CHR. Section 1.1 outlines the history of programming languages with particular attention to CHR and related languages. Then, Section 1.2 introduces CHR using examples. Section 1.3 gives some preliminaries which will be used during the thesis. Subsequentely, Section 1.4 introduces the syntax and the operational and declarative semantics for the first CHR language proposed. Finally, the methodologies to solve the problem of trivial non-termination related to propagation rules are discussed in Section 1.5. Chapter 2 introduces a compositional semantics for CHR where the propagation rules are considered. In particular, Section 2.1 contains the definition of the semantics. Hence, Section 2.2 presents the compositionality results. Afterwards Section 2.3 expounds upon the correctness results. Chapter 3 presents a particular program transformation known as unfolding. This transformation needs a particular syntax called annotated which is introduced in Section 3.1 and its related modified operational semantics !0t is presented in Section 3.2. Subsequently, Section 3.3 defines the unfolding rule and prove its correctness. Then, in Section 3.4 the problems related to the replacement of a rule by its unfolded version are discussed and this in turn gives a correctness condition which holds for a specific class of rules. Section 3.5 proves that confluence and termination are preserved by the program modifications introduced. Finally, Chapter 4 concludes by discussing related works and directions for future work.

Corporate Venture Capital: How established firms use external resources to create new competencies

This Doctoral Dissertation is triggered by an emergent trend: firms are increasingly referring to investments in corporate venture capital (CVC) as means to create new competencies and foster the search for competitive advantage through the use of external resources. CVC is generally defined as the practice by non-financial firms of placing equity investments in entrepreneurial companies. Thus, CVC can be interpreted (i) as a key component of corporate entrepreneurship - acts of organizational creation, renewal, or innovation that occur within or outside an existing organization– and (ii) as a particular form of venture capital (VC) investment where the investor is not a traditional and financial institution, but an established corporation. My Dissertation, thus, simultaneously refers to two streams of research: corporate strategy and venture capital. In particular, I directed my attention to three topics of particular relevance for better understanding the role of CVC. In the first study, I moved from the consideration that competitive environments with rapid technological changes increasingly force established corporations to access knowledge from external sources. Firms, thus, extensively engage in external business development activities through different forms of collaboration with partners. While the underlying process common to these mechanisms is one of knowledge access, they are substantially different. The aim of the first study is to figure out how corporations choose among CVC, alliance, joint venture and acquisition. I addressed this issue adopting a multi-theoretical framework where the resource-based view and real options theory are integrated. While the first study mainly looked into the use of external resources for corporate growth, in the second work, I combined an internal and an external perspective to figure out the relationship between CVC investments (exploiting external resources) and a more traditional strategy to create competitive advantage, that is, corporate diversification (based on internal resources). Adopting an explorative lens, I investigated how these different modes to renew corporate current capabilities interact to each other. More precisely, is CVC complementary or substitute to corporate diversification? Finally, the third study focused on the more general field of VC to investigate (i) how VC firms evaluate the patent portfolios of their potential investee companies and (ii) whether the ability to evaluate technology and intellectual property varies depending on the type of investors, in particular for what concern the distinction between specialized versus generalist VCs and independent versus corporate VCs. This topic is motivated by two observations. First, it is not clear yet which determinants of patent value are primarily considered by VCs in their investment decisions. Second, VCs are not all alike in terms of technological experiences and these differences need to be taken into account.

Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

Seeing and feeling the body

Recognizing one’s body as separate from the external world plays a crucial role in detecting external events, and thus in planning adequate reactions to them. In addition, recognizing one’s body as distinct from others’ bodies allows remapping the experiences of others onto one’s sensory system, providing improved social understanding. In line with these assumptions, two well-known multisensory mechanisms demonstrated modulations of somatosensation when viewing both one’s own and someone else’s body: the Visual Enhancement of Touch (VET) and the Visual Remapping of Touch (VRT) effects. Vision of the body, in the former, and vision of the body being touched, in the latter, enhance tactile processing. The present dissertation investigated the multisensory nature of these mechanisms and their neural bases. Further experiments compared these effects for viewing one’s own body or viewing another person’s body. These experiments showed important differences in multisensory processing for one’s own body, and for other bodies, and also highlighted interactions between VET and VRT effects. The present experimental evidence demonstrated that a multisensory representation of one’s body – underlie by a high order fronto-parietal network - sends rapid modulatory feedback to primary somatosensory cortex, thus functionally enhancing tactile processing. These effects were highly spatially-specific, and depended on current body position. In contrast, vision of another person’s body can drive mental representations able to modulate tactile perception without any spatial constraint. Finally, these modulatory effects seem sometimes to interact with high order information, such as emotional content of a face. This allows one’s somatosensory system to adequately modulate perception of external events on the body surface, as a function of its interaction with the emotional state expressed by another individual.

From core rigidities to dynamic capabilities: the role of external knowledge. A multiple case study

This study focuses on the processes of change that firms undertake to overcome conditions of organizational rigidity and develop new dynamic capabilities, thanks to the contribution of external knowledge. When external contingencies highlight firms’ core rigidities, external actors can intervene in change projects, providing new competences to firms’ managers. Knowledge transfer and organizational learning processes can lead to the development of new dynamic capabilities. Existing literature does not completely explain how these processes develop and how external knowledge providers, as management consultants, influence them. Dynamic capabilities literature has become very rich in the last years; however, the models that explain how dynamic capabilities evolve are not particularly investigated. Adopting a qualitative approach, this research proposes four relevant case studies in which external actors introduce new knowledge within organizations, activating processes of change. Each case study consists of a management consulting project. Data are collected through in-depth interviews with consultants and managers. A large amount of documents supports evidences from interviews. A narrative approach is adopted to account for change processes and a synthetic approach is proposed to compare case studies along relevant dimensions. This study presents a model of capabilities evolution, supported by empirical evidence, to explain how external knowledge intervenes in capabilities evolution processes: first, external actors solve gaps between environmental demands and firms’ capabilities, changing organizational structures and routines; second, a knowledge transfer between consultants and managers leads to the creation of new ordinary capabilities; third, managers can develop new dynamic capabilities through a deliberate learning process that internalizes new tacit knowledge from consultants. After the end of the consulting project, two elements can influence the deliberate learning process: new external contingencies and changes in the perceptions about external actors.

The European External Action Service and the Implementation of the 'Union Method' in European Foreign Policy

The European External Action Service (EEAS or Service) is one of the most significant and most debated innovations introduced by the Lisbon Treaty. This analysis intends to explain the anomalous design of the EEAS in light of its function, which consists in the promotion of external action coherence. Coherence is a principle of the EU legal system, which requires synergy in the external actions of the Union and its Members. It can be enforced only through the coordination of European policy-makers' initiatives, by bridging the gap between the 'Communitarian' and intergovernmental approaches. This is the 'Union method' envisaged by A. Merkel: "coordinated action in a spirit of solidarity - each of us in the area for which we are responsible but all working towards the same goal". The EEAS embodies the 'Union method', since it is institutionally linked to both Union organs and Member States. It is also capable of enhancing synergy in policy management and promoting unity in international representation, since its field of action is delimited not by an abstract concern for institutional balance but by a pragmatic assessment of the need for coordination in each sector. The challenge is now to make sure that this pragmatic approach is applied with respect to all the activities of the Service, in order to reinforce its effectiveness. The coordination brought by the EEAS is in fact the only means through which a European foreign policy can come into being: the choice is not between the Community method and the intergovernmental method, but between a coordinated position and nothing at all.

Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

Understanding the Combined Role of Internal and External Factors in New Service Development Process within the Professional Knowledge Intensive Business Service Firms

Our research asked the following main questions: how the characteristics of professionals service firms allow them to successfully innovate in exploiting through exploring by combining internal and external factors of innovation and how these ambidextrous organisations perceive these factors; and how do successful innovators in professional service firms use corporate entrepreneurship models in their new service development processes? With a goal to shed light on innovation in professional knowledge intensive business service firms’ (PKIBS), we concluded a qualitative analysis of ten globally acting law firms, providing business legal services. We analyse the internal and factors of innovation that are critical for PKIBS’ innovation. We suggest how these firms become ambidextrous in changing environment. Our findings show that this kind of firms has particular type of ambidexterity due to their specific characteristics. As PKIBS are very dependant on its human capital, governance structure, and the high expectations of their clients, their ambidexterity is structural, but also contextual at the same time. In addition, we suggest 3 types of corporate entrepreneurship models that international PKIBS use to enhance innovation in turbulent environments. We looked at how law firms going through turbulent environments were using corporate entrepreneurship activities as a part of their strategies to be more innovative. Using visual mapping methodology, we developed three types of innovation patterns in the law firms. We suggest that corporate entrepreneurship models depend on successful application of mainly three elements: who participates in corporate entrepreneurship initiatives; what are the formal processes that enhances these initiatives; and what are the policies applied to this type of behaviour.

Methane production through anaerobic digestion of dedicated energy crops

Methane yield of ligno-cellulosic substrates (i.e. dedicated energy crops and agricultural residues) may be limited by their composition and structural features. Hence, biomass pre-treatments are envisaged to overcome this constraint. This thesis aimed at: i) assessing biomass and methane yield of dedicated energy crops; ii) evaluating the effects of hydrothermal pre-treatments on methane yield of Arundo; iii) investigating the effects of NaOH pre-treatments and iv) acid pre-treatments on chemical composition, physical structure and methane yield of two dedicated energy crops and one agricultural residue. Three multi-annual species (Arundo, Switchgrass and Sorghum Silk), three sorghum hybrids (Trudan Headless, B133 and S506) and a maize, as reference for AD, were studied in the frame of point i). Results exhibit the remarkable variation in biomass yield, chemical characteristics and potential methane yield. The six species alternative to maize deserve attention in view of a low need of external inputs but necessitate improvements in biodegradability. In the frame of point ii), Arundo was subjected to hydrothermal pre-treatments at different temperature, time and acid catalyst (with and without H2SO4). Pre-treatments determined a variable effect on methane yield: pre-treatments without acid catalyst achieved up to +23% CH4 output, while pre-treatments with H2SO4 catalyst incurred a methanogenic inhibition. Two biomass crops (Arundo and B133) and an agricultural residue (Barley straw) were subject to NaOH and acid pre-treatments, in the frame of point iii) and iv), respectively. Different pre-treatments determined a change of chemical and physical structure and an increase of methane yield: up to +30% and up to +62% CH4 output in Arundo with NaOH and acid pre-treatments, respectively. It is thereby demonstrated that pre-treatments can actually enhance biodegradability and subsequent CH4 output of ligno-cellulosic substrates, although pre-treatment viability needs to be evaluated at the level of full scale biogas plants in a perspective of profitable implementation.

Portfolio Approaches in Constraint Programming

Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance. In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core. We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.