Interactive foundations of computing

The claim that interactive systems have richer behavior than algorithms is surprisingly easy to prove. Turing machines cannot model interaction machines (which extend Turing machines with interactive input/output) because interaction is not expressible by a finite initial input string. Interaction machines extend the Chomsky hierarchy, are modeled by interaction grammars, and precisely capture fuzzy concepts like open systems and empirical computer science. Computable functions cannot model real-world behavior because functions are too strong an abstraction, sacrificing the ability to model time and other real-world properties to realize formal tractability.Part I of this paper examines extensions to interactive models for algorithms, machines, grammars, and semantics, while Part II considers the expressiveness of different forms of interaction. Interactive identity machines are already more powerful than Turing machines, while noninteractive parallelism and distribution are algorithmic. The extension of Turing to interaction machines parallels that of the lambda to the pi calculus. Asynchronous and nonserializable interaction are shown to be more expressive than sequential interaction (multiple streams are more expressive than a single stream).In Part III, it is shown that interaction machines cannot be described by sound and complete first-order logics (a form of Godel incompleteness), and that incompleteness is inherently necessary to realize greater expressiveness. In the final section the robustness of interactive models in expressing open systems, programming in the large, graphical user interfaces, and agent-oriented artificial intelligence is compared to the robustness of Turing machines. Less technical discussion of these ideas may be found in [25–27]. Applications of interactive models to coordination, objects and components, patterns and frameworks, software engineering, and AI are examined elsewhere [28,29].The propositions P1-P36 embody the principal claims, while observations 01 through 040 provide additional insights.     

The ontological deficiencies of process modeling in practice

Business process modeling is widely regarded as one of the most popular forms of conceptual modeling. However, little is known about the capabilities and deficiencies of process modeling grammars and how existing deficiencies impact actual process modeling practice. This paper is a first contribution towards a theory-driven, exploratory empirical investigation of the ontological deficiencies of process modeling with the industry standard Business Process Modeling Notation (BPMN). We perform an analysis of BPMN using a theory of ontological expressiveness. Through a series of semi-structured interviews with BPMN adopters we explore empirically the actual use of this grammar. Nine ontological deficiencies related to the practice of modeling with BPMN are identified, for example, the capture of business rules and the specification of process decompositions. We also uncover five contextual factors that impact on the use of process modeling grammars, such as tool support and modeling conventions. We discuss implications for research and practice, highlighting the need for consideration of representational issues and contextual factors in decisions relating to BPMN adoption in organizations.     

Mining the Semantic Web

In the Semantic Web vision of the World Wide Web, content will not only be accessible to humans but will also be available in machine interpretable form as ontological knowledge bases. Ontological knowledge bases enable formal querying and reasoning and, consequently, a main research focus has been the investigation of how deductive reasoning can be utilized in ontological representations to enable more advanced applications. However, purely logic methods have not yet proven to be very effective for several reasons: First, there still is the unsolved problem of scalability of reasoning to Web scale. Second, logical reasoning has problems with uncertain information, which is abundant on Semantic Web data due to its distributed and heterogeneous nature. Third, the construction of ontological knowledge bases suitable for advanced reasoning techniques is complex, which ultimately results in a lack of such expressive real-world data sets with large amounts of instance data. From another perspective, the more expressive structured representations open up new opportunities for data mining, knowledge extraction and machine learning techniques. If moving towards the idea that part of the knowledge already lies in the data, inductive methods appear promising, in particular since inductive methods can inherently handle noisy, inconsistent, uncertain and missing data. While there has been broad coverage of inducing concept structures from less structured sources (text, Web pages), like in ontology learning, given the problems mentioned above, we focus on new methods for dealing with Semantic Web knowledge bases, relying on statistical inference on their standard representations. We argue that machine learning research has to offer a wide variety of methods applicable to different expressivity levels of Semantic Web knowledge bases: ranging from weakly expressive but widely available knowledge bases in RDF to highly expressive first-order knowledge bases, this paper surveys statistical approaches to mining the Semantic Web. We specifically cover similarity and distance-based methods, kernel machines, multivariate prediction models, relational graphical models and first-order probabilistic learning approaches and discuss their applicability to Semantic Web representations. Finally we present selected experiments which were conducted on Semantic Web mining tasks for some of the algorithms presented before. This is intended to show the breadth and general potential of this exiting new research and application area for data mining.     

Detecting Faults in Context-Aware Adaptation

Internetware applications are context-aware. They adapt their behavior based on environmental changes. However, faulty adaptation may arise when these applications face unanticipated situations. Such adaptation faults can be difficult to detect at design time. One promising approach is to statically analyze model-based context-aware applications exhaustively for all potential faults. However, it suffers from expressiveness and precision problems. To address these limitations, we propose in this paper a dynamic adaptation model (AM) approach. AM offers increased expressive power to model complex adaptation rules, and guarantees soundness in its fault detection. In addition, AM deploys an incremental rule evaluation (IRE) technique to cater for context-aware applications, such that it can effciently handle environmental changes in its fault detection. We evaluated AM using both simulated and real-world experiments with two context-aware applications. The experimental results confirmed that AM can detect real faults missed by existing work, and avoid numerous false warnings that were misreported otherwise.     

Expressive interfaces

Analysis of expressiveness in human gesture can lead to new paradigms for the design of improved human-machine interfaces, thus enhancing users participation and experience in mixed reality applications and context-aware mediated environments. The development of expressive interfaces decoding the highly affective information gestures convey opens novel perspectives in the design of interactive multimedia systems in several application domains: performing arts, museum exhibits, edutainment, entertainment, therapy, and rehabilitation. This paper describes some recent developments in our research on expressive interfaces by presenting computational models and algorithms for the real-time analysis of expressive gestures in human full-body movement. Such analysis is discussed both as an example and as a basic component for the development of effective expressive interfaces. As a concrete result of our research, a software platform named EyesWeb was developed (). Besides supporting research, EyesWeb has also been employed as a concrete tool and open platform for developing real-time interactive applications.     

A graph grammar-based formal validation of object-process diagrams

Two basic requirements from a system’s conceptual model are correctness and comprehensibility. Most modeling methodologies satisfy only one of these apparently contradicting requirements, usually comprehensibility, leaving aside problems of correctness and ambiguousness that are associated with expressiveness. Some formal modeling languages do exist, but in these languages a complete model of a complex system is fairly complicated to understand. Object-process methodology (OPM) is a holistic systems modeling methodology that combines the two major aspects of a system—structure and behavior—in one model, providing mechanisms to manage the complexity of the model using refinement-abstraction operations, which divide a complex system into many interconnected diagrams. Although the basic syntax and semantics of an OPM model are defined, they are incomplete and leave room for incorrect or ambiguous models. This work advances the formal definition of OPM by providing a graph grammar for creating and checking OPM diagrams. The grammar provides a validation methodology of the semantic and syntactic correctness of a single object-process diagram.     

Parsing with restricted quantification: an initial demonstration1

The primary goal of this paper is to illustrate how smaller deductive search spaces can be obtained by extending a logical language with restricted quantification and tailoring an inference system to this extension. The illustration examines the search spaces for a bottom-up parse of a sentence with a series of four strongly equivalent grammars. The grammars are stated in logical languages of increasing expressiveness, each restatement resulting in a more concise grammar and a smaller search space. A secondary goal is to point out an area where further research could yield results useful to the design of efficient parsers, particularly for grammatical formalisms that rely heavily on feature systems.     

Filtering Multi-Instance Problems to Reduce Dimensionality in Relational Learning

Attribute-value based representations, standard in today's data mining systems, have a limited expressiveness. Inductive Logic Programming provides an interesting alternative, particularly for learning from structured examples whose parts, each with its own attributes, are related to each other by means of first-order predicates. Several subsets of first-order logic (FOL) with different expressive power have been proposed in Inductive Logic Programming (ILP). The challenge lies in the fact that the more expressive the subset of FOL the learner works with, the more critical the dimensionality of the learning task. The Datalog language is expressive enough to represent realistic learning problems when data is given directly in a relational database, making it a suitable tool for data mining. Consequently, it is important to elaborate techniques that will dynamically decrease the dimensionality of learning tasks expressed in Datalog, just as Feature Subset Selection (FSS) techniques do it in attribute-value learning. The idea of re-using these techniques in ILP runs immediately into a problem as ILP examples have variable size and do not share the same set of literals. We propose here the first paradigm that brings Feature Subset Selection to the level of ILP, in languages at least as expressive as Datalog. The main idea is to first perform a change of representation, which approximates the original relational problem by a multi-instance problem. The representation obtained as the result is suitable for FSS techniques which we adapted from attribute-value learning by taking into account some of the characteristics of the data due to the change of representation. We present the simple FSS proposed for the task, the requisite change of representation, and the entire method combining those two algorithms. The method acts as a filter, preprocessing the relational data, prior to the model building, which outputs relational examples with empirically relevant literals. We discuss experiments in which the method was successfully applied to two real-world domains.     

Synchrony vs Asynchrony in Communication Primitives

We study, from the expressiveness point of view, the impact of synchrony in the communication primitives that arise when combining together some common and useful programming features like arity of data, communication medium and possibility of pattern matching. For some primitives, we show how their synchronous version can be encoded in their asynchronous counterpart via a fully abstract encoding, thus proving that the two versions have the same expressive power. For the remaining primitives, we prove that no ‘reasonable’ encoding can exist, thus proving that synchrony adds expressiveness to the language.     

Semantic web reasoners and languages

Semantic web reasoners and languages enable the semantic web to function. Some of the latest reasoning models developed in the last few years are: DLP, FaCT, RACER, Pellet, MSPASS, CEL, Cerebra Engine, QuOnto, KAON2, HermiT and others. Some software tools such as Protégé, Jena and others also have been developed, which provide inferencing as well as ontology development and management environments. These reasoners usually differ in their inference procedures, supporting logic, completeness of reasoning, expressiveness and implementation languages. Various semantic web languages with increasing expressive power continue to be developed for describing web services. We survey the some of the more recent languages like OWL-S (Ontology Web Language-Schema), WSML (Web Service Modeling Language), SWRL (Semantic Web Rule Language) and others that have been tested in early use. We also survey semantic web reasoners and their relationship to these languages.     

XSWRL,an Extended Semantic Web Rule Language and prototype implementation

Although the OWL (Web Ontology Language) and SWRL (Semantic Web Rule Language) add considerable expressiveness to the Semantic Web they do have expressive limitations. For some reasoning problems it is necessary to infer the existence of new individuals satisfying stated condition. This kind of problems can not be fully resolved by OWL and SWRL. We present the XSWRL (Extended Semantic Web Rule Language), an extension to SWRL, to overcome these problems. XSWRL introduces existentially quantified variables to rules. XSWRL extends SWRL in a syntactically and semantically coherent manner. We show that while the expressiveness of the Semantic Web language is improved, the undecidability and infinite chains are brought on. We define the inseparable set of atoms to separate XSWRL rules, and discuss a prototype implementation of reasoning support for XSWRL.     

A framework for traversing dense annotation lattices

Pattern matching, or querying, over annotations is a general purpose paradigm for inspecting, navigating, mining, and transforming annotation repositories—the common representation basis for modern pipelined text processing architectures. The open-ended nature of these architectures and expressiveness of feature structure-based annotation schemes account for the natural tendency of such annotation repositories to become very dense, as multiple levels of analysis get encoded as layered annotations. This particular characteristic presents challenges for the design of a pattern matching framework capable of interpreting ‘flat’ patterns over arbitrarily dense annotation lattices. We present an approach where a finite state device applies (compiled) pattern grammars over what is, in effect, a linearized ‘projection’ of a particular route through the lattice. The route is derived by a mix of static grammar analysis and runtime interpretation of navigational directives within an extended grammar formalism; it selects just the annotations sequence appropriate for the patterns at hand. For expressive and efficient pattern matching in dense annotations stores, our implemented approach achieves a mix of lattice traversal and finite state scanning by exposing a language which, to its user, provides constructs for specifying sequential, structural, and configurational constraints among annotations.     

Incorporating ontology-based semantics into conceptual modelling

With the increasing complexity of applications and user needs, recent research has shifted from a data-information level to a human semantic level interaction. Research has begun to address the increasing use and development of ontologies in various applications, strongly motivated by the semantic web initiative. However, existing conceptual models are not rich enough to incorporate ontologies in one single conceptual schema. To improve this situation, it is necessary to refine modelling formalisms and make them more expressive while ensuring they remain semantically sound. We argue that conceptual modelling methodologies would be semantically richer if they were able to express the semantics of a domain that arises in concrete application scenarios. This paper investigates the incorporation of ontologies into three popular conceptual modelling methodologies, presenting the Ontological Entity-Relationship (OntoER) model, Ontological Object Role Modelling (OntoORM) and the Ontological Unified Modelling Language (OntoUML) class diagram. An extended conceptual framework for modelling ontologies and a transformation algorithm for mapping ontological constructs to relational schemata are provided so that querying the database through the conceptualisation of the database can be managed.     

On the expressiveness of second-order spider diagrams

Existing diagrammatic notations based on Euler diagrams are mostly limited in expressiveness to monadic first-order logic with an order predicate. The most expressive monadic diagrammatic notation is known as spider diagrams of order. A primary contribution of this paper is to develop and formalise a second-order diagrammatic logic, called second-order spider diagrams, extending spider diagrams of order. A motivation for this lies in the limited expressiveness of first-order logics. They are incapable of defining a variety of common properties, like ‘is even’, which are second-order definable. We show that second-order spider diagrams are at least as expressive as monadic second-order logic. This result is proved by giving a method for constructing a second-order spider diagram for any regular expression. Since monadic second-order logic sentences and regular expressions are equivalent in expressive power, this shows second-order spider diagrams can express any sentence of monadic second-order logic.     

Confluence of aspects for sequence diagrams

The last decade has seen several aspect language proposals for UML 2 sequence diagrams. Aspects allow the modeler to define crosscutting concerns of sequence diagrams and to have these woven with the sequence diagrams of a so-called base model, in order to create a woven model. In a real-world scenario, there may be multiple aspects applicable to the same base model. This raises the need to analyse the set of aspects to identify possible aspect interactions (dependencies and conflicts) between applications of aspects. We call a set of aspects terminating if they may not be applied infinitely many times for any given base model. Furthermore, we call a set of terminating aspects confluent, if they, for any given base model, always yield the same final result regardless of the order in which they are applied. Since confluence must hold for any base model, this is a much stronger result than many of the current approaches that have addressed detection of aspect interactions limited to a specific base model. Our aspects are specified using standard sequence diagrams with some extensions. In this paper, we present a confluence theory specialized for our highly expressive aspect language. For the most expressive aspects, we prove that confluence is undecidable. For another class of aspects with considerable expressiveness, we prescribe an algorithm to check confluence. This algorithm is based on what we call an extended critical pair analysis. These results are useful both for modelers and researchers working with sequence diagram aspects and for researchers wanting to establish a confluence theory for other aspect-oriented modelling or model transformation approaches.     

Specification Diagrams for Actor Systems

Specification diagrams (SD's) are a novel form of graphical notation for specifying open distributed object systems. The design goal is to define notation for specifying message-passing behavior that is expressive, intuitively understandable, and that has formal semantic underpinnings. The notation generalizes informal notations such as UML's Sequence Diagrams and broadens their applicability to later in the design cycle. Specification diagrams differ from existing actor and process algebra presentations in that they are not executable per se; instead, like logics, they are inherently more biased toward specification. In this paper we rigorously define the language syntax and semantics and give examples that show the expressiveness of the language, how properties of specifications may be asserted diagrammatically, and how it is possible to reason rigorously and modularly about specification diagrams.