A Coalgebraic Semantics for Epistemic Programs

This paper gives a fresh look at my previous work on “epistemic actions” and information updates in distributed systems, from a coalgebraic perspective. I show that the “relational” semantics of epistemic programs, given in [BMS2] in terms of epistemic updates, can be understood in terms of functors on the category of coalgebras and natural transformations associated to them. Then, I introduce a new, alternative, more refined semantics for epistemic programs: programs as “epistemic coalgebras”. I argue for the advantages of this second semantics, from a semantic, heuristic, syntactical and proof-theoretic point of view. Finally, as a step towards a generalization, I show these concepts make sense for other functors, and that apparently unrelated concepts, such as Bayesian belief updates and process transformations, can be seen to arise in the same way as our “epistemic actions”.     

SweetWiki: A semantic wiki

Everyone agrees that user interactions and social networks are among the cornerstones of “Web 2.0”. Web 2.0 applications generally run in a web browser, propose dynamic content with rich user interfaces, offer means to easily add or edit content of the web site they belong to and present social network aspects. Well-known applications that have helped spread Web 2.0 are blogs, wikis, and image/video sharing sites; they have dramatically increased sharing and participation among web users. It is possible to build knowledge using tools that can help analyze users’ behavior behind the scenes: what they do, what they know, what they want. Tools that help share this knowledge across a network, and that can reason on that knowledge, will lead to users who can better use the knowledge available, i.e., to smarter users. Wikipedia, a wildly successful example of web technology, has helped knowledge-sharing between people by letting individuals freely create and modify its content. But Wikipedia is designed for people—today's software cannot understand and reason on Wikipedia's content. In parallel, the “semantic web”, a set of technologies that help knowledge-sharing across the web between different applications, is starting to gain attraction. Researchers have only recently started working on the concept of a “semantic wiki”, mixing the advantages of the wiki and the technologies of the semantic web. In this paper we will present a state-of-the-art of semantic wikis, and we will introduce SweetWiki, an example of an application reconciling two trends of the future web: a semantically augmented web and a web of social applications where every user is an active provider as well as a consumer of information. SweetWiki makes heavy use of semantic web concepts and languages, and demonstrates how the use of such paradigms can improve navigation, search, and usability.     

Ascertaining Mathematical Theorems

Whereas to most logicians, the word “theorem” refers to any statement which has been shown to be true, to mathematicians, the word “Theorem” is, relatively speaking, rarely applied, and denotes something far more special. In this paper, we examine some of the underlying reasons behind this difference in terminology, and we show how this discrepancy might be exploited, in order to build a computer system which automatically selects the latter type of “Theorems” from amongst the former. Indeed, we have begun building the automated discovery system MATHsAiD, the design of which is based upon our research. We provide some preliminary results produced by this system, and compare these results to Theorems appearing in various mathematics textbooks.     

A Practical Approach to Partial Functions in CVC Lite

Most verification approaches assume a mathematical formalism in which functions are total, even though partial functions occur naturally in many applications. Furthermore, although there have been various proposals for logics of partial functions, there is no consensus on which is “the right” logic to use for verification applications. In this paper, we propose using a three-valued Kleene logic, where partial functions return the “undefined” value when applied outside of their domains. The particular semantics are chosen according to the principle of least surprise to the user; if there is disagreement among the various approaches on what the value of the formula should be, its evaluation is undefined. We show that the problem of checking validity in the three-valued logic can be reduced to checking validity in a standard two-valued logic, and describe how this approach has been successfully implemented in our tool, CVC Lite.     

Generic Trace Theory

Trace semantics has been defined for various non-deterministic systems with different input/output types, or with different types of “non-determinism” such as classical non-determinism (with a set of possible choices) vs. probabilistic non-determinism. In this paper we claim that these various forms of “trace semantics” are instances of a single categorical construction, namely coinduction in a Kleisli category. This claim is based on our main technical result that an initial algebra in the category of sets and functions yields a final coalgebra in the Kleisli category, for monads with a suitable order structure. The proof relies on coincidence of limits and colimits, like in the work of Smyth and Plotkin.     

Teaching programming: A spiral approach to syntax and semantics

Coupling the recently proposed syntactic/semantic model of programmer behavior [1] with classic educational psychological theories yields new insights to teaching programming to novices. These new insights should make programming education more natural to students. alleviate “computer shock” (the analog of “math anxiety” [2]) and promote the development of widespread “computer literacy”.The spiral approach is the parallel acquisition of syntactic and semantic knowledge in a sequence which provokes student interest by using meaningful examples, builds on previous knowledge, is in harmony with the student's cognitive skills, provides reinforcement of recently acquired material and develops confidence through successful accomplishment of increasingly difficult tasks. The relationship of structured programming and flowcharts to the spiral approach is discussed.     

Conversation rebuilding: From the foreign language classroom to implementation in an intelligent tutoring system

This paper shows how an innovative “communicative” technique in teaching foreign languages—Conversation Rebuilding (CR)—readily lends itself to implementation in an Intelligent Tutoring System (ITS). Classroom language teachers using CR get students to formulate acceptable utterances in a foreign idiom by starting from rough approximations (using words the students know) and gradually zeroing in on the utterance which a native speaker of that idiom might produce in a similar setting. The ITS presented here helps students do the “zeroing in” optimally. It lets them express themselves temporarily in an “interlingua” (i.e., in their own kind of French or English or whatever they are studying), as long as they make something of their communicative intent clear, that is, as long as the System can find a semantic starting point on which to build. The ITS then prods the students to express themselves more intelligibly, starting from the “key” elements (determined by a heuristic based on how expert classroom teachers proceed) and taking into consideration the students' past successful or unsuccessful attempts at communication. To simplify system design and programming, however, conversations are “constrained”: students playact characters in set dialogs and aim at coming up with what the characters actually say (not what they could possibly say). While most Intelligent Computer Assisted Language Learning (ICALL) focuses the attention of students on norms to acquire, the ICALL implementation of CR presented in this paper focuses the attention of students on saying something—indeed, almost anything—to keep the conversation going and get some kind of meaning across to the other party. It sees successful language acquisition primarily as the association of forms with intent, not simply as the conditioning of appropriate reflexes or the elaboration/recall of conceptualized rules (which are the by-products of successful communication). Thus, in espousing this hard-line communicative approach, the present paper makes a first, non-trivial point: ICALL researchers might usefully begin by investigating what the more able teachers are doing in the classroom, rather than by building elaborate computer simulations of out-dated practices, as happens all too often. The paper then goes on to describe the architecture of a prototype ITS based on CR—one that the authors have actually implemented and tested—for the acquisition of English as a foreign language. A sample learning session is transcribed to illustrate the man-machine interaction. Concluding remarks show how the present-day limits of ICALL (and Artificial Intelligence in general) can be partially circumvented by the strategy implemented in the program, i.e. by making the students feel they are creatively piloting an interaction rather than being tested by an unimaginative machine.     

Completeness of Continuation Models for λμ-Calculus

We show that a certain simple call-by-name continuation semantics of Parigot's λ_μ-calculus is complete. More precisely, for every λ_μ-theory we construct a cartesian closed category such that the ensuing continuation-style interpretation of λ_μ, which maps terms to functions sending abstract continuations to responses, is full and faithful. Thus, any λ_μ-category in the sense of L. Ong (1996, in “Proceedings of LICS '96,” IEEE Press, New York) is isomorphic to a continuation model (Y. Lafont, B. Reus, and T. Streicher, “Continuous Semantics or Expressing Implication by Negation,” Technical Report 93-21, University of Munich) derived from a cartesian-closed category of continuations. We also extend this result to a later call-by-value version of λ_μ developed by C.-H. L. Ong and C. A. Stewart (1997, in “Proceedings of ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Paris, January 1997,” Assoc. Comput. Mach. Press, New York).     

A methodology for expressing CIM reference architectures

TNO is doing research in many areas of industrial automation and is heavily involved in European projects financed by R&D programmes such as Esprit, Eureka and Brite, and in many ISO and CEN standardization activities. From this experience it becomes clear that the I of Integration in CIM has not only to do with the integration of the so-called “islands of automation” but also with the integration of ”islands of manufacturing”: how we can improve the transfer of manufacturing knowledge. We have to increase the semantic content of our integration approaches, so that not only can computer scientist be involved, but also people from the companies we are trying to help, and people who are responsible for the development of new CIM components. The real problem is not a problem of technical integration of computers, but much more a “conceptual modelling” problem. Fundamental questions are, for instance, how we can, on the semantic level really required, model information transfer upstream and downstream in the product life cycle. Based on the analysis of existing CIM projects such as CAD*I, CIM- OSA, Open CAM Systems (Esprit I) IMPACT (Esprit II), CAM-I's CIM Architecture, the Danish Principal model for CIM, and more, we developed a generic and reusable CIM reference architecture. This architecture shows manufacturing activities, real and information flow objects, CIM components and industrial automation standards like STEP, MAP, TOP, EDIFACT, MMS etc. in an integrated way. In this paper we describe the CIM base model used to express the CIM reference architecture and give some details of the CIM reference architecture itself.     

Compositional State Space Reduction Using Untangled Actions

We propose a compositional technique for efficient verification of networks of parallel processes. It is based on an automatic analysis of LTSs of individual processes (using a failure-based equivalence which preserves divergences) that determines their sets of “conflict-free” actions, called untangled actions. Untangled actions are compositional, i.e. synchronisation on untangled actions will not destroy their “conflict-freedom”. For networks of processes, using global untangled actions derived from local ones, efficient reduction algorithms have been devised for systems with a large number of small processes running in parallel.     

Dynamic Submodel Integration Using an Offer-Accept Discrete Event Simulation

Newer approaches for modelling travel behaviour require a new approach to integrated spatial economic modelling. Travel behaviour modelling is increasingly disaggregate, econometric, dynamic, and behavioural. A fully dynamic approach to urban system modelling is described, where interactions are characterized as two agents interacting through discrete events labelled as “offer” or “accept”. This leads to a natural partition of an integrated urban model into submodels based on the category of what is being exchanged, the type of agent, and the time and place of interaction.Where prices (or price-like signals such as congested travel times) exist to stimulate supply and/or to suppress demand, the dynamic change in prices can be represented either behaviourally, as individual agents adjust their expectations in response to their personal history and the history of the modelled region, or with an “auctioneer” from micro-economic theory, who adjusts average prices. When no auctioneers are used, the modelling system can use completely continuous representations of both time and space.Two examples are shown. The first is a demonstration of a continuous-time continuous-space transaction simulation with simple agents representing businesses and households. The second shows how an existing model—the Oregon TLUMIP project for statewide land-use and transport modelling—can be adapted into the paradigm.     

Comprehension for Coalgebras

The notion of an endofunctor having “greatest subcoalgebras” is introduced as a form of comprehension. This notion is shown to be instrumental in giving a systematic and abstract proof of the existence of limits for coalgebras—proved earlier by Worrell and by Gumm & Schröder. These insights, in dual form, are used to reinvestigate colimits for algebras in terms of “least quotient algebras”—leading to a uniform approach to limits of coalgebras and colimits of algebras. Finally, at an abstract level of fibrations, an equivalence is established between having greatest subcoalgebras (in a base category of types) and greatest invariants (in a total category of predicates).     

Critical success factors revisited: success and failure cases of information systems for senior executives

The literature suggests the existence of critical success factors (CSFs) for the development of information systems that support senior executives. Our study of six organizations gives evidence for this notion of CSFs. The study further shows an interesting pattern, namely that companies either “get it right”, and essentially succeed on all CSFs, or “get it completely wrong”, that is, fall short on each of the CSFs. Among the six cases for which data were collected through in-depth interviews with company executives, three organizations seemed to manage all the CSFs properly, while two others managed all CSFs poorly. Only one organization showed a mixed scorecard, managing some factors well and some not so well. At the completion of the study, this organization could neither be judged as a success, nor as a failure. This dichotomy between success and failure cases suggests the existence of an even smaller set of “meta-success” factors. Based on our findings, we speculate that these “meta-success” factors are “championship”, “availability of resources”, and “link to organization objectives”.     

Extensional PERs

A class of Partial Equivalence Relations (PERs) is described such that the resulting full subcategory of the realizability universe has the expected properties of a good category of CPOs; that is, it is a Cartesian closed category and every endomorphism has a canonical fixed point. Moreover, the reflection functor into the subcategory of strict maps (usually called the “lifting operation”) yields a good notion of “partial map,” a necessary condition if one wishes to maintain a connection between strict maps and partial maps. It is shown that all functors that arise in practice have canonical invariant objects; hence a host of domain equations are guaranteed to have solutions.     

Calculators are needlessly bad

In the two decades hand-held calculators have been readily available, there has been ample time to develop a usable design and to educate the consumer public into choosing quality devices. This article reviews a representative calculator that is “state of the art” and shows it has an execrable design. The design is shown to be confusing and essentially non-mathematical. Substantial evidence is presented that illustrates the inadequate documentation, bad implementation, feature interaction, and feature incoherence. These problems are shown to be typical of calculators generally. Despite the domain (arithmetic) being well defined, the design problems are profound, widespread, confusing—and needless. Worrying questions are begged: about design quality control, about consumer behaviour, and about the role of education—both at school level (training children to acquiesce to bad design) and at university level (training professionals to design unusable products). The article concludes with recommendations.“The problem of efficient and uniform notations is perhaps the most serious one facing the mathematical public.” Florian Cajori (1993)“[. . .] contrivances adapted to peculiar purposes [. . .] and what is worse than all, a profusion of notations (when we regard the whole science) which threaten, if not duly corrected, to multiply our difficulties instead of promoting our progress.” Charles Babbage, quoted in Cajori (1993).     

Designing a semantic bliki system to support different types of knowledge and adaptive learning

Though blogs and wikis have been used to support knowledge management and e-learning, existing blogs and wikis cannot support different types of knowledge and adaptive learning. A case in point, types of knowledge vary greatly in category and viewpoints. Additionally, adaptive learning is crucial to improving one’s learning performance. This study aims to design a semantic bliki system to tackle such issues. To support various types of knowledge, this study has developed a new social software called “bliki” that combines the advantages of blogs and wikis. This bliki system also applies Semantic Web technology to organize an ontology and a variety of knowledge types. To aid adaptive learning, a function called “Book” is provided to enable learners to arrange personalized learning goals and paths. The learning contents and their sequences and difficulty levels can be specified according to learners’ metacognitive knowledge and collaborative activities. An experiment is conducted to evaluate this system and the experimental results show that this system is able to comprehend various types of knowledge and to improve learners’ learning performance.