Model checking is the most effective means of verifying the correctness of asynchronous designs, and state space exploration is central to model checking. Although model checking can achieve very high verification coverage, the high degree of concurrency in asynchronous designs often leads to state explosion during state space exploration. To inhibit this explosion, our approach builds on the ideas of compositional verification. In our approach, a design modeled in a high level description is partitioned into a set of parallel components. Before state space exploration, each component is paired with an over-approximated environment to decouple it from the rest of the design. Then, a global state transition graph is constructed by reducing and incrementally composing component state transition graphs. We take great care during reduction and composition to preserve all failures found during the initial state space exploration of each component. To further reduce complexity, interface constraints are automatically derived for the over-approximated environment of each component. We prove that our approach is conservative in that false positive results are never produced. The effectiveness of our approach is demonstrated by the experimental results of several case studies showing that our approach can verify designs that cannot be handled by traditional at approaches. The experiments also show that constraints can reduce the size of the global state transition graph and prevent some false failures.

Software systems are now pervasive throughout our world. The reliability of these systems is an urgent necessity. A large degree of research effort on increasing software reliability is dedicated to requirements, architecture, design, implementation and testing---activities that are performed before system deployment. While such approaches have become substantially more advanced, software remains buggy and failures remain expensive. We take a radically different approach to reliability from previous approaches, namely contract-driven data structure repair for runtime error recovery, where erroneous executions of deployed software are corrected on-the-fly using rich behavioral contracts. Our key insight is to transform the software contract---which gives a high level description of the expected behavior---to an efficient implementation which repairs the erroneous data structures in the program state upon an error. To improve efficiency, scalability, and effectiveness of repair, in addition to rich behavioral contracts, we leverage the current erroneous state, dynamic behavior of the program, as well as repair history and abstraction. A core technical problem our approach to repair addresses is construction of structurally complex data that satisfy desired properties. We present a novel structure generation technique based on dynamic programming---a classic optimization approach---to utilize the recursive nature of the structures. We use our technique for constraint-based testing. It provides better scalability than previous work. We applied it to test widely-used web browsers and found some known and unknown bugs. Our use of dynamic programming in structure generation opens a new future direction to tackle the scalability problem of data structure repair. This research advances our ability to develop correct programs. For programs that already have contracts, error recovery using our approach can come at a low cost. The same contracts can be used for systematically testing code before deployment using existing as well as our new techniques. Thus, we enable a novel unification of software verification and error recovery. / text

A Culture of Dissonance: Wassily Kandinsky, Atonality, and Abstraction by Lynn Edward Boland, Ph.D. Supervisor: Linda D. Henderson Wassily Kandinsky's interest in music as a source for abstraction in painting has often been noted in the scholarship on his art. However, no studies have sufficiently explained how the artist employed musical strategies, especially as he was developing his abstract style in the first decade of the twentieth century. Kandinsky's looked primarily to Arnold Schoenberg's new musical idioms and theories, and he was deeply inspired by highly dissonant music, but his ideas were set within a much broader context that further suggested and encouraged the expressive and transformative power of dissonance. By the late nineteenth century, extended passages of dissonance were common in musical compositions. At the same time, the concept of dissonance as a positive force was suggested in a wide range of late nineteenth-century literature, including the writings of Friedrich [should be this spelling throughout] Nietzsche, occult authors, popular texts on physics and experimental psychology, as well as within music and art theory. Close readings of Kandinsky's theoretical texts and selected works of art provide insights into how he might have understood and employed these concepts in his formation of an abstract style. Kandinsky's paintings Impression III (Concert) of 1911 and Composition VII of 1913 are the primary artistic foci of this study, along with his book Concerning the Spiritual in Art and the anthology Der Blaue Reiter, which he co-edited. This dissertation will seek to restore the concept of musical dissonance and its application in the visual arts to its historical context for Kandinsky. This will facilitate more informed formal analyses of Schoenberg's music and Kandinsky's paintings, which, in turn, suggest strategies of atonal musical composition applied to abstract painting. Additionally, this dissertation will establish an artistic context of visual dissonance that goes beyond Kandinsky, including artistic movements in France and Russia, allowing additional comparisons and a consideration of the larger impact of these ideas. / text

Concurrent systems are getting more complex with the advent of multi-core processors and the support of concurrent programs. However, errors of concurrent systems are too subtle to detect with the traditional testing and simulation. Model checking is an effective method to verify concurrent systems by exhaustively searching the complete state space exhibited by a system. However, the main challenge for model checking is state explosion, that is the state space of a concurrent system grows exponentially in the number of components of the system. The state space explosion problem prevents model checking from being applied to systems in realistic size. After decades of intensive research, a large number of methods have been developed to attack this well-known problem. Compositional verification is one of the promising methods that can be scalable to large complex concurrent systems. In compositional verification, the task of verifying an entire system is divided into smaller tasks of verifying each component of the system individually. The correctness of the properties on the entire system can be derived from the results from the local verification on individual components. This method avoids building up the global state space for the entire system, and accordingly alleviates the state space explosion problem. In order to facilitate the application of compositional verification, several issues need to be addressed. The generation of over-approximate and yet accurate environments for components for local verification is a major focus of the automated compositional verification. This dissertation addresses such issue by proposing two abstraction refinement methods that refine the state space of each component with an over-approximate environment iteratively. The basic idea of these two abstraction refinement methods is to examine the interface interactions among different components and remove the behaviors that are not allowed on the components' interfaces from their corresponding state space. After the extra behaviors introduced by the over-approximate environment are removed by the abstraction refinement methods, the initial coarse environments become more accurate. The difference between these two methods lies in the identification and removal of illegal behaviors generated by the over-approximate environments. For local properties that can be verified on individual components, compositional reasoning can be scaled to large systems by leveraging the proposed abstraction refinement methods. However, for global properties that cannot be checked locally, the state space of the whole system needs to be constructed. To alleviate the state explosion problem when generating the global state space by composing the local state space of the individual components, this dissertation also proposes several state space reduction techniques to simplify the state space of each component to help the compositional minimization method to generate a much smaller global state space for the entire system. These state space reduction techniques are sound and complete in that they keep all the behaviors on the interface but do not introduce any extra behaviors, therefore, the same verification results derived from the reduced global state space are also valid on the original state space for the entire system. An automated compositional verification framework integrated with all the abstraction refinement methods and the state space reduction techniques presented in this dissertation has been implemented in an explicit model checker Platu. It has been applied to experiments on several non-trivial asynchronous circuit designs to demonstrate its scalability. The experimental results show that our automated compositional verification framework is effective on these examples that are too complex for the monolithic model checking methods to handle.

Heterogeneous multi-agent systems are currently used in a wide variety of situations, including search and rescue, military applications, and off-world exploration, however it is difficult to understand the actions of these systems or naturalistically assign these mixed teams to tasks. These agents, which may be human, robot or software, have different capabilities but will need to coordinate effectively with humans in order to operate. The first and largest contributing factor to this challenge is the processing, understanding and representing of elements of the natural world in a manner that can be utilized by artificial agents. A second contributing factor is that current abstractions and robot architectures are ill-suited to address this problem. This dissertation addresses the lack of a high-level abstraction for the naturalistic coordination of teams of heterogeneous robots, humans and other agents through the development of roles. Roles are a fundamental concept of social science that may provide this necessary abstraction. Roles are not a new concept and have been used in a number of related areas. This work draws from these fields and constructs a coherent and usable model of roles for robotics. This research is focussed on answering the following question: Can the use of social roles enable the naturalistic coordinated operation of robots in a mixed setting? In addition to this primary question, related research includes defining the key concepts important to artificial systems, providing a mapping and implementation from these concepts to a usable robot framework and identifies a set of robot-specific roles used for human-robot interaction. This research will benefit both the artificial intelligence agent and robotics communities. It poses a fundamental contribution to the multi-agent community because it extends and refines the role concept. The application of roles in a principled and complete implementation is a novel contribution to both software and robotic agents. The creation of an open source operational architecture which supports taskable robots is also a major contribution.

This dissertation investigates how the project of abstraction, initiated in interwar Europe, was reconstructed, continued, and transformed in mid-twentieth-century South America. Through an examination of the work and thought of three key artists (Tomás Maldonado of Argentina, Alejandro Otero of Venezuela, and Lygia Clark of Brazil), it posits historical continuity and universality as both central problems of mid-century South American projects of abstraction and potential avenues toward a new understanding of their historical specificity. I identify three key features of interwar abstraction that were consciously continued in the work of Maldonado, Otero, and Clark: the adoption of abstraction not as a style, but as a progressive teleology with a linear history and singular goal; the ambition to reach the end of painting as an autonomous activity and integrate abstraction into the built environment; and the belief in the power of abstraction to forge new subjects and collectivities. In all three cases, the encounter of a universalistic project with particular socio-historical realities had resonances unanticipated by their European predecessors. Whereas abstraction in interwar Europe was intimately tied to struggles against bourgeois subjectivity and for a new form of egalitarian collectivity, artists in mid-century South America were rather faced with accelerated, state-driven developmentalism and the emergence of populist politics. Against this background, I demonstrate how each artist envisioned abstraction as a tool to contribute to or disrupt newly emerging forms of collectivity, contrasting Maldonado's insistence on an international, class-based collective, Otero's efforts to forge a modern national community, and Clark's advocating for a contingent intersubjectivity as a way of resisting top-down projects of collectivity. Finally, I investigate how the engagement with ideas of continuity and universality, as exemplified by these three artists, intersected with broader conceptions of historical progress and development circulating in Latin America between the Second World War and the Cuban Revolution. The rise and fall of abstraction in South America during this period, I conclude, was closely linked to the dream of catching up with "universal history" and its eventual abandonment. / History of Art and Architecture

In language, there exists a distinction between abstract words and concrete words. It can be said that abstract words refer to generic concepts, while concrete words pertain to physical actions or objects associated with physical movement. With respect to the linguistic community, it is often claimed that French words function at a higher degree of abstraction than English words. However, this claim lacks empirical evidence. The present study aims to examine the usage of concrete and abstract words in word association tasks, which are part of Cultura: an intercultural, web-based project that brings foreign language students from different countries and linguistic backgrounds together in a telecollaborative exchange of ideas. Specifically, this study examines the degrees of abstraction of generic nouns in French and English. / text

The transportation routing map is increasingly used in various transportation network modeling applications such as vehicle navigation and traffic assignment modeling. A typical navigation GIS map contains all detailed road facility layers and may not be as computationally efficient as a lower-resolution map for path finding. A lower-resolution transportation routing map retains only route-finding related roadways and is efficient for path finding but may result in sub-optimal routes because of misclassification links. With the goal in balancing the traffic analysis requirement of intended application and computation requirements of transportation navigation and traffic assignment, the systematic abstraction of the lower-resolution transportation routing map from high resolution map is an important and non-trivial task. For vehicle navigation applications, the traffic analysis requirement is the shortest path quality. An innovative transportation routing map abstraction method or Connectivity Enhancement Algorithm (CEA) is proposed to deal with vehicle navigation application routing map abstraction. The algorithm starts from a low-resolution network and keeps updating the map by adding links and nodes when it processes each search set. The outcome of the algorithm is an abstract map that retains the original detailed map's hierarchical structure with quality topological connectivity at a significant computations saving. With the development of traffic assignment modeling, a detailed network is desired to describe the real world traffic network. It is the consensus that one should not directly apply a GIS map blind-sight without a systematic approach and unnecessarily overuse the network details causes excessive run time. The traffic analysis requirement of those applications is the dynamic user equilibrium (DUE) condition network performance is identical or near-identical with high resolution network. The lowest network resolution level that meets the requirements of emerging traffic analysis is not easy to determine. The proposed traffic analysis network abstraction method gives a solution for this problem. It is an iterative network abstraction approach and considers the link travel time with DUE traffic condition. The case study and numerical analysis prove that the two network abstraction methods are sound and promising. The transportation routing map abstraction method could detect most misclassification links and is robust for different network scales. The abstracted navigation map provides the identical or near-identical SP cost/travel time for any OD pair while the computation burden is much lighter than that on original map. In another hand, the case studies about the traffic analysis network abstraction tell that the method converges very quick and the rendered the abstracted network that has lowest resolution of network or least links and nodes but the DUE condition network performance or trips cost/travel time is much closer to that on the original map.

Magistro baigiamajame darbe tyrinėta verslo informacinė sistema jos išsivystymas ir metodologija panaudojant komponentais pagrįstą metodą. Metodas parodo kaip naudoti komponentais - orientuotą paradigmą, kad išvystytume sistemą visuose trijuose verslo lygmenyse. Darbe pristatoma pati sąvoka ir jos principai, paradigmos verslo plėtojimo kontekste. Metodas siūlo naudoti komponentų abstrakciją kaip realizavimo techniką daugumos bendrų taikomųjų principų, kurie gali sumažinti integruotos verslo informacinės sistemos plėtojimo sudėtingumą ir palaikymą. Integruotos organizacijų informacinės sistemos į darnią visumą sujungia verslo informacijos apdorojimo ir programinės bei techninės įrangos komponentus. Tokių sistemų kūrimas, sudėtinės dalys, modulinė architektūra turi savo specifinių ypatumų. Šio darbo tikslas – ištirti komponentinės paradigmos taikymo galimybes organizacijų integruotoms informacinėms sistemoms kurti, suformuluoti svarbiausias problemas, kurias reikia spręsti, norint projektuoti ir realizuoti šitokias sistemas. Magistro darbe pateiktos problemas, kurios egzistuoja formalizuojant integruotas verslo sistemas remiantis komponentine paradigma. Nagrinėjama komponentinė sistemų kūrimo paradigma, siekiant perkelti komponentinių programų sistemų kūrimo idėjas į organizacijų integruotų informacinių sistemų lygmenį. Nagrinėjamos komponento ir jo pagrindinių dalių sampratos, įvairių abstrakcijos lygmenų komponentų ypatumai, jų jungimo būdai. Suformuluoti reikalavimai... [toliau žr. visą tekstą] / This final master degree paper analysis the integrated enterprise information system, its development and methodology using component based method. This method shows how the component - oriented paradigm can be used for developing system in all three layers of enterprise. The paper presents the main concept and its principles, context of paradigm through the enterprise development. The method offers the usage of component abstraction like the technique of realisation. The main principles can reduce the difficultness and maintenance of integrated enterprise information system. The integrated enterprise information system connects enterprise information treatment, software and hardware components to the totality. The establishment of this kind of systems, its components, modular architecture has its specific peculiarities. The main objective of the paper – is to research a possibility of using the componentised paradigm in the establishment of the integrated enterprise information systems. Also, to analyse the main problems, which has to be solved if you want to engineer and implement this kind of systems. The master degree paper shows the problems, which exists in formalization of integrated enterprise systems based on the componentised paradigm. It analysis the componentised system development paradigm, persuading the transferring of componentised system establishment ideas into the integrated information system layer. The paper analysis the main concepts of the component... [to full text]

Recent years have shown a broad spectra of tangible interfaces or TUI's, based upon interaction with music, but also other interfaces containing ubiquitous computing. This is an interesting field due to how engaging music can be and work as connector between people. But the field of human computer interaction has some explorational properties. This paper presents an idea of abstraction with a tangible interface for creating music. The idea behind abstraction of the interface is to engage the user(s) in exploring the artifact, rather than explaining the artifact to the user what can and cannot be done with the artifact.