Search

The Vienna Definition Language (VDL) is a programming language for defining programming languages. It allows us to describe precisely the execution of the set of all programs of a programming language. However, the Vienna Definition Language is important not only as one definition technique among many others but as an illustration of a new information-structure-oriented approach to the study of programming languages. The paper may be regarded as a case study in the information structure modeling of programming languages, as well as an introduction to a specific modeling technique. Part 1 includes a brief review and comparison of techniques of language definition, and then introduces the basic data structures and data structure manipulation operators that are used to define programming languages. Part 2 considers the definition of sets of data structures. Part 3 introduces the notation for specifying VDL instructions, and illustrates the definition of a simple language for arithmetic expression evaluation by giving the complete sequence of states (snapshots) that arise during the evaluation of an expression. Part 4 defines a simple block structure language in VDL and considers certain basic design issues for such languages in a more general context. Part 5 introduces an alternative definition of the block structure language defined in Part 4, proves the equivalence of the two definitions, and briefly reviews recent work on proving the equivalence of interpreters. An Appendix considers the definition of VDL in VDL. This paper may be read at a number of different levels. The reader who is interested in a quick introduction to the basic definition techniques of VDL need read only Section 1.3 and Part 3. The reader who is interested in a deeper understanding of block structure languages should emphasize Part 4, while the reader concerned with proofs of equivalence of interpreters will be interested in Part 5. [ABSTRACT FROM AUTHOR]

A model checker is an automatic tool that traverses a specific structure (normally a Kripke structure referred as the model M) to check the satisfaction of some (temporal) logical property f. This is formally stated as $${M \models f}$$ . For some formal notations, the model M of a specification S (written in a formal language L) can be described as a labelled transition system (LTS). Specifically, it is not clear in general how usual tools such as SPIN, FDR, PAT, etc., create the LTS representation from a given process. Although one expects the coherence of the LTS generation with the semantics of L, it is completely hidden inside the model checker itself. In this paper we show how to create a model checker for L, using a development approach based on its operational semantics. We use a systematic semantics embedding and the formal modeling using logic programming and analysis (FORMULA) framework to this end. We illustrate our strategy considering the formal language COMPASS modelling language (CML)-a new language that was based on CSP, VDM and the refinement calculus proposed for modelling and analysis of systems of systems. As FORMULA is based on satisfiability modulo theories solving, our model checker can handle communications and predicates involving data with infinite domains by building and manipulating a symbolic LTS. This goes beyond the capabilities of traditional CSP model checkers such as FDR and PAT. Moreover, we show how to reduce time and space complexities by simple semantic modifications in the embedding. This allows a more semantics-preserving tuning. Finally, we show a real implementation of our model checker in an integrated development platform for CML and its practical use on an industrial case study. [ABSTRACT FROM AUTHOR]

Most of the activities usually performed by Web users are today effectively supported by using appropriate metadata that make the Web practically readable by software agents operating as users' assistants. While the original use of metadata mostly focused on improving queries on Web knowledge bases, as in the case of SPARQL-based applications on RDF data, other approaches have been proposed to exploit the semantic information contained in metadata for performing more sophisticated knowledge discovery tasks. Finding semantic associations between Web data seems a promising framework in this context, since it allows that novel, potentially interesting information can emerge by the Web's sea, deeply exploiting the semantic relationships represented by metadata. However, the approaches for finding semantic associations proposed in the past do not seem to consider how Web entities are logically collected into groups, that often have a complex hierarchical structure. In this paper, we focus on the importance of taking into account this additional information, and we propose an approach for finding semantic associations which would not emerge without considering the structure of the data groups. Our approach is based on the introduction of a new metadata model, that is an extension of the direct, labelled graph allowing the possibility to have nodes with a hierarchical structure. To evaluate our approach, we have implemented it on the top of an existing recommender system for Web users, experimentally analyzing the introduced advantages in terms of effectiveness of the recommendation activity. [ABSTRACT FROM AUTHOR]

For over a decade, researchers in formal methods have tried to create formalisms that permit natural specification of systems and allow mathematical reasoning about their correctness. The availability of fully automated reasoning tools enables non-experts to use formal methods effectively?their responsibility reduces to specifying the model and expressing the desired properties. Thus, it is essential that these properties be represented in a language that is easy to use, sufficiently expressive and succinct. Linear-time temporal logic (LTL) is a formalism that has been used extensively by researchers for program specification and verification. One of the desired properties of LTL formulas is closure under stuttering. That is, we do not want the interpretation of formulas to change over traces where some states are repeated. This property is important from both practical and theoretical prospectives; all properties which are closed under stuttering can be expressed in LTL -X?a fragment of LTL without the ?next? operator. However, it is often difficult to express properties in this fragment of LTL. Further, determining whether a given LTL property is closed under stuttering is PSPACE-complete. In this paper, we introduce a notion of edges of LTL formulas and present a formal theory of closure under stuttering. Edges allow natural modelling of systems with events. Our theory enables syntactic reasoning about whether the resulting properties are closed under stuttering. Finally, we apply the theory to the pattern-based approach of specifying temporal formulas. [ABSTRACT FROM AUTHOR]

Many applications require semantic understanding of short texts, and inferring discriminative and coherent latent topics is a critical and fundamental task in these applications. Conventional topic models largely rely on word co-occurrences to derive topics from a collection of documents. However, due to the length of each document, short texts are much more sparse in terms of word co-occurrences. Recent studies show that the Dirichlet Multinomial Mixture (DMM) model is effective for topic inference over short texts by assuming that each piece of short text is generated by a single topic. However, DMM has two main limitations. First, even though it seems reasonable to assume that each short text has only one topic because of its shortness, the definition of "shortness" is subjective and the length of the short texts is dataset dependent. That is, the single-topic assumption may be too strong for some datasets. To address this limitation, we propose to model the topic number as a Poisson distribution, allowing each short text to be associated with a small number of topics (e.g., one to three topics). This model is named PDMM. Second, DMM (and also PDMM) does not have access to background knowledge (e.g., semantic relations between words) when modeling short texts. When a human being interprets a piece of short text, the understanding is not solely based on its content words, but also their semantic relations. Recent advances in word embeddings offer effective learning of word semantic relations from a large corpus. Such auxiliary word embeddings enable us to address the second limitation. To this end, we propose to promote the semantically related words under the same topic during the sampling process, by using the generalized Pólya urn (GPU) model. Through the GPU model, background knowledge about word semantic relations learned from millions of external documents can be easily exploited to improve topic modeling for short texts. By directly extending the PDMM model with the GPU model, we propose two more effective topic models for short texts, named GPU-DMM and GPU-PDMM. Through extensive experiments on two real-world short text collections in two languages, we demonstrate that PDMM achieves better topic representations than state-of-the-art models, measured by topic coherence. The learned topic representation leads to better accuracy in a text classification task, as an indirect evaluation. Both GPU-DMM and GPU-PDMM further improve topic coherence and text classification accuracy. GPUPDMM outperforms GPU-DMM at the price of higher computational costs. [ABSTRACT FROM AUTHOR]

We address the problem of automatic recognition of functional parts of man-made 3D shapes in the presence of significant geometric and topological variations. We observe that under such challenging circumstances, the context of a part within a 3D shape provides important cues for learning the semantics of shapes. We propose to model the context as structural relationships between shape parts and use them, in addition to part geometry, as cues for functionality recognition. We represent a 3D shape as a graph interconnecting parts that share some spatial relationships. We model the context of a shape part as walks in the graph. Similarity between shape parts can then be defined as the similarity between their contexts, which in turn can be efficiently computed using graph kernels. This formulation enables us to: (1) find part-wise semantic correspondences between 3D shapes in a nonsupervised manner and without relying on user-specified textual tags, and (2) design classifiers that learn in a supervised manner the functionality of the shape components. We specifically show that the performance of the proposed context-aware similarity measure in finding part-wise correspondences outperforms geometry-only-based techniques and that contextual analysis is effective in dealing with shapes exhibiting large geometric and topological variations. [ABSTRACT FROM AUTHOR]

This article presents a semantics-based context-aware dynamic service composition framework that composes an application through combining distributed components based on the semantics of components and contexts of users. The proposed framework consists of Component Service Model with Semantics (CoSMoS), Component Runtime Environment (CoRE), and Semantic Graph based Service Composition (SeGSeC). CoSMoS models the semantics of components and contexts of users. CoRE is a middleware to support CoSMoS on various distributed computing technologies. SeGSeC is a mechanism to compose an application by synthesizing its workflow based on the semantics of components and contexts of users. The proposed framework is capable of composing applications requested in a natural language by leveraging the semantic information of components. The proposed framework composes applications differently to individual users based on their contexts and preferences. The proposed framework acquires user preferences from user-specified rules and also via learning. The proposed framework also adapts to dynamic environments by autonomously composing a new application upon detecting context change. This article describes the design and mechanism of the proposed framework, and also presents simulation experiments to evaluate the proposed framework. [ABSTRACT FROM AUTHOR]

Semantics of description languages for complex systems are a central issue for implementing verification methods such as model checking. This technique is employed to verify systems by inspecting only a small state space that represents its potential behaviors. This paper presents a generalized operational semantics of the modelling language promela that provides the theoretical basis to introduce this promising method in the model checker SPIN. The generalization consists of identifying language aspects affected by the abstraction. Using these aspects as parameters, it is possible to obtain and relate different interpretations of the language. The new semantics provides a framework to reason about how to construct the tool aspin as an extension of spin. [ABSTRACT FROM AUTHOR]

This article introduces a named entity matching model that makes use of both semantic and phonetic evidence. The matching of semantic and phonetic information is captured by a unified framework via a bipartite graph model. By considering various technical challenges of the problem, including order insensitivity and partial matching, this approach is less rigid than existing approaches and highly robust. One major component is a phonetic matching model which exploits similarity at the phoneme level. Two learning algorithms for learning the similarity information of basic phonemic matching units based on training examples are investigated. By applying the proposed named entity matching model, a mining system is developed for discovering new named entity translations from daily Web news. The system is able to discover new name translations that cannot be found in the existing bilingual dictionary. [ABSTRACT FROM AUTHOR]