Guards,Bounds, and Generalized Semantics

Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) satisfiability on general assignment models for arbitrary first-order formulas. In particular, we give a new straightforward reduction from the former notion to the latter. We also show how a perspective shift to general assignment models provides a new look at the fixed-point extension LFP(FO) of first-order logic, making it decidable. Next, we relate guarded syntax to earlier quantifier restriction strategies for achieving effective axiomatizability in second-order logic – pointing at analogies with ‘persistent’ formulas, which are essentially in the Bounded Fragment of many-sorted first-order logic. Finally, we look at some further unexplored directions, including the systematic use of ‘quasi-models’ as a semantics by itself.     

How to Pass a Turing Test

I advocate a theory of syntactic semantics as a way of understanding how computers can think (and how the Chinese-Room-Argument objection to the Turing Test can be overcome): (1) Semantics, considered as the study of relations between symbols and meanings, can be turned into syntax – a study of relations among symbols (including meanings) – and hence syntax (i.e., symbol manipulation) can suffice for the semantical enterprise (contra Searle). (2) Semantics, considered as the process of understanding one domain (by modeling it) in terms of another, can be viewed recursively: The base case of semantic understanding –understanding a domain in terms of itself – is syntactic understanding. (3) An internal (or narrow), first-person point of view makes an external (or wide), third-person point of view otiose for purposes of understanding cognition.     

Reduction Semantics and Formal Analysis of Orc Programs

Orc is a language for orchestration of web services developed by J. Misra that offers simple, yet powerful and elegant, constructs to program sophisticated web orchestration applications. The formal semantics of Orc poses interesting challenges, because of its real-time nature and the different priorities of external and internal actions. In this paper, building upon our previous SOS semantics of Orc in rewriting logic, we present a much more efficient reduction semantics of Orc, which is provably equivalent to the SOS semantics thanks to a strong bisimulation. We view this reduction semantics as a key intermediate stage towards a future, provably correct distributed implementation of Orc, and show how it can naturally be extended to a distributed actor-like semantics. We show experiments demonstrating the much better performance of the reduction semantics when compared to the SOS semantics. Using the Maude rewriting logic language, we also illustrate how the reduction semantics can be used to endow Orc with useful formal analysis capabilities, including an LTL model checker. We illustrate these formal analysis features by means of an online auction system, which is modeled as a distributed system of actors that perform Orc computations.     

Mental models, visual reasoning and interaction in information visualization: a top-down perspective

Although previous research has suggested that examining the interplay between internal and external representations can benefit our understanding of the role of information visualization (InfoVis) in human cognitive activities, there has been little work detailing the nature of internal representations, the relationship between internal and external representations and how interaction is related to these representations. In this paper, we identify and illustrate a specific kind of internal representation, mental models, and outline the high-level relationships between mental models and external visualizations. We present a top-down perspective of reasoning as model construction and simulation, and discuss the role of visualization in model based reasoning. From this perspective, interaction can be understood as active modeling for three primary purposes: external anchoring, information foraging, and cognitive offloading. Finally we discuss the implications of our approach for design, evaluation and theory development.     

Contextual Labelled Semantics for Higher-order Process Calculi

In this paper, we study a contextual labelled transition semantics for Higher-Order process calculi. The labelled transition semantics are relatively clean and simple, and corresponding bisimulation equivalence can be easily formulated based on it. Besides we develop a novel approach to reason about behaviours of a higher-order substituted process P{Q/X}, based on which we can directly prove a very important result – factorisation theorem. To show the correspondence between our semantics and the well-established ones, we characterize our bisimulation in a version of barbed equivalence.     

Analyzing the Adequacy of Interaction Paradigms in Artificial Reality Experiences

In Artificial Reality experiences, that is, interactive, unencumbered, full-body, 2D vision-based virtual reality (VR) experiences (heirs of the seminal Videoplace by Myron Krueger), there are two possible interaction paradigms, namely, first-person and third-person—which differ significantly from the classic VR first- and third-person notions. Up until now, these two paradigms had not been compared or objectively analyzed in such systems. Moreover, most systems are based on the third-person paradigm without a specific justification, most probably due to the influence of the original Videoplace system and because it is the only paradigm available in commercial development tools and leisure systems. For example, many rehabilitation projects have chosen to use these VR systems because of their many advantages. However, most of these projects and research have blindly adopted the third-person paradigm. Hence, the field of virtual rehabilitation has analyzed the beneficial properties of these systems without considering the first-person paradigm that could potentially present better adequacy. To find and understand potential differences between the two paradigms, we have defined an application categorization from which we developed two full-body interactive games and set up an experiment to analyze each game in both paradigms. We studied how 39 participants played these games and we quantitatively and qualitatively analyzed how each paradigm influenced the experience, the activity and the behavior of the users and the efficiency in accomplishing the required goals. We present the results of these experiments and their general implications, and especially for virtual rehabilitation due to the potential impact these systems may have in the well-being of many people.     

Semantics of digital networks containing indeterminate modules

We discuss a formal model based upon dataflow, usable for high-level digital hardware design, among other things. One of our goals is to give a denotational semantics for this model, which includes indeterminate modules. While it is wellknown that denotational semantics for networks containing only determinate modules can be simply expressed as a composition of stream functions, this approach has previously been shown unacceptable for networks with indeterminate modules. Our approach is to devise composition rules based on modelling a network by the set of its possible behaviors, i.e. sequences of computational events, where each event is the appearance or consumption of a token on a data path. A sequence of such events is called ahistory and a set of such histories is called anarchive. We give composition rules that allow us to derive an archive for a network from the archive of its constituents. We show how causal and operational constraints on network behavior can be inferred from the specification of archives. We also present a construction which allows us to obtain the denotation of networks containing loops by a process of successive approximations. This construction is carried out using a construction resembling the category-theoretic notion oflimit, which differs from that of more traditional domain theory.Prakash Panangadenreceived his M.Sc. in Physics from IIT Kanpur in 1975. He earned a MS in Physics from the University of Chicago in 1978 and a Ph.D. from the University of Wisconsin-Milwaukee in 1980. For the last 3 years he has worked in the area of distributed systems and semantics and has been an instructor at the University of Utah where he earned an MS in Computer Science in 1985. Since August 1985 he has been an assistant professor in the computer science department at Cornell University.Robert M. Kelleris a Professor of Computer Science at the University of Utah. He received the B.S. and M.S.E.E. from Washington University, and the Ph.D. from the University of California, Berkeley. From 1970–1976 he was an Assistant Professor of Electrical Engineering at Princeton University. He has held visiting appointments at Stanford University and Lawrence Livermore National Laboratories. His research contributions are in the area of theory of concurrent processing, parallel program verification, parallel computer architecture, and implementation of functional languages. His current research interests deal with numerous topics relating to multiprocessor implementations of highlevel languages, particularly functional and logic languages, and the construction of reduction and data-flow computation models.     

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”.     

Generating a learning stance through perspective-taking in a virtual environment

Emerging media technologies such as virtual environments present a unique opportunity to examine the effects of perspective-taking on processes of human learning. In these environments it is possible for learners to immerse themselves in a unique visual perspective—such as that of a competent actor—and experience the ways they allocate their attention as they perform critical tasks in a domain. This study investigates whether the opportunity to experience a first-person perspective of actions in a virtual world simulation benefits learning compared to a third-person, disembodied perspective of those same events. Measures of performance within the simulation and post-assessment activities including a diagramming task indicate significant advantages for participants who received the first-person perspective. These participants had a better memory for the important tasks and task-related elements of the simulation; they committed fewer errors and exhibited less help-seeking behavior than participants with a third-person perspective. Results are described in terms of a virtual environment’s ability to generate a learning stance through person-centered perspective-taking, and potential implications for the design of instructional computer technologies are discussed.     

A Rewriting Logic Approach to Operational Semantics (Extended Abstract)

This paper shows how rewriting logic semantics (RLS) can be used as a computational logic framework for operational semantic definitions of programming languages. Several operational semantics styles are addressed: big-step and small-step structural operational semantics (SOS), modular SOS, reduction semantics with evaluation contexts, and continuation-based semantics. Each of these language definitional styles can be faithfully captured as an RLS theory, in the sense that there is a one-to-one correspondence between computational steps in the original language definition and computational steps in the corresponding RLS theory. A major goal of this paper is to show that RLS does not force or pre-impose any given language definitional style, and that its flexibility and ease of use makes RLS an appealing framework for exploring new definitional styles.     

Effects of first- and third-person perspectives created using a head-mounted display on dart-throwing accuracy

Virtual Reality - The first-person perspective (1PP) and third-person perspective (3PP) have both been adopted in video games. The 1PP can induce a strong sense of immersion, and the 3PP allows...     

Timed Semantics of Message Sequence Charts Based on Timed Automata

Message Sequence Charts (MSCs) provide a way for quick and easily understandable modelling of concurrent systems. Apart from their intuitive semantics easily deduced from their visual syntax, there is a formally defined semantics—Unfortunately, the semantics intuitively assigned to them is sometimes at odds with the formal semantics. In this paper, we will show an alternative approach to the semantics of MSCs, which will enable us to formally model their timed behaviour. Furthermore, we show how some generalizations of ordering events can lead to a language better suited to model real-world requirements. To ease the task of analyzing (High-Level) MSCs, we identify a subclass of those which can be translated into finite (timed of untimed) automata and specify the translation, thus laying the foundation for model checking.     

Semantics as a Foundation for Psychology: A Case Study of Wason's Selection Task

We review the various explanations that have been offered toaccount for subjects' behaviour in Wason's famous selection task. Weargue that one element that is lacking is a good understanding ofsubjects' semantics for the key expressions involved, and anunderstanding of how this semantics is affected by the demands the taskputs upon the subject's cognitive system. We make novel proposals inthese terms for explaining the major content effects of deonticmaterials. Throughout we illustrate with excerpts from tutorialdialogues which motivate the kinds of analysis proposed. Our long termgoal is an integration of the various insights about conditionalreasoning on offer from different cognitive science methodologies. Thepurpose of this paper is to try to draw the attention of logicians andsemanticists to this area, since we believe that empirical investigationof the cognitive processes involved could benefit from semanticanalyses.     

浅析产品语义的通俗化

本文对语义学在产品设计中的体现进行了分析,对产品语义的通俗化问题进行了研究,概括了一些有助于产品语义运用的通俗化方法,并在此基础上对产品语义标准库存在的必要性进行了阐述。以期待通过产品语义的通俗化研究,能够使产品与使用者之间的沟通更加的方便,达到人与产品之间的相互协调。     

Reasoning with Intensional Negative Adjectivals: Semantics, Pragmatics, and Context

Intensional negative adjectives alleged , artificial , fake , false , former , and toy are unusual adjectives that depending on context may or may not be restricting functions. A formal theory of their semantics, pragmatics, and context that uniformly accounts for their complex mathematical and computational characteristics and captures some peculiarities of individual adjectives is presented.
Such adjectives are formalized as new concept builders, negation‐like functions that operate on the values of intensional properties of the concepts denoted by their arguments and yield new concepts whose intensional properties have values consistent with the negation of the old values. Understanding these new concepts involves semantics, pragmatics and context‐dependency of natural language. It is argued that intensional negative adjectives can be viewed as a special‐purpose, weaker, conntext‐dependent negationin natural language. The theory explains and predicts many inferences licensed by expressions involving such adjectives. Implementation of sample examples demonstrates its computational feasibility. Computation of context‐dependent interpretation is discussed.
The theory allows one to enhance a knowledge representation system with similar concept building, negation‐like, context‐dependent functions, the availability of which appears to be a distinct characteristic of natural languages.     

Semantics of probabilistic programs

This paper presents two complementary but equivalent semantics for a high level probabilistic programming language. One of these interprets programs as partial measurable functions on a measurable space. The other interprets programs as continuous linear operators on a Banach space of measures. It is shown how the ordered domains of Scott and others are embedded naturally into these spaces. We use the semantics to prove a general result about probabilistic programs, namely, that a program's behavior is completely determined by its action on fixed inputs.     

Linearity, Persistence and Testing Semantics in the Asynchronous Pi-Calculus

In [C. Palamidessi, V. Saraswat, F. Valencia and B. Victor. On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi Calculus. LICS 2006:59–68, 2006] the authors studied the expressiveness of persistence in the asynchronous π-calculus (Aπ) wrt weak barbed congruence. The study is incomplete because it ignores the issue of divergence. In this paper, we present an expressiveness study of persistence in the asynchronous π-calculus (Aπ) wrt De Nicola and Hennessy's testing scenario which is sensitive to divergence. Following [C. Palamidessi, V. Saraswat, F. Valencia and B. Victor. On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi Calculus. LICS 2006:59–68, 2006], we consider Aπ and three sub-languages of it, each capturing one source of persistence: the persistent-input calculus (PIAπ), the persistent-output calculus (POAπ) and persistent calculus (PAπ). In [C. Palamidessi, V. Saraswat, F. Valencia and B. Victor. On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi Calculus. LICS 2006:59–68, 2006] the authors showed encodings from Aπ into the semi-persistent calculi (i.e., POAπ and PIAπ) correct wrt weak barbed congruence. In this paper we prove that, under some general conditions, there cannot be an encoding from Aπ into a (semi)-persistent calculus preserving the must testing semantics.     

Transfinite Semantics in the Form of Greatest Fixpoint

Transfinite semantics is a semantics according to which program executions can continue working after an infinite number of steps. Such a view of programs can be useful in the theory of program transformations.So far, transfinite semantics have been succesfully defined for iterative loops. This paper provides an exhaustive definition for semantics that enable also infinitely deep recursion.The definition is actually a parametric schema that defines a family of different transfinite semantics. As standard semantics also match the same schema, our framework describes both standard and transfinite semantics in a uniform way.All semantics are expressed as greatest fixpoints of monotone operators on some complete lattices. It turns out that, for transfinite semantics, the corresponding lattice operators are cocontinuous. According to Kleene’s theorem, this shows that transfinite semantics can be expressed as a limit of iteration which is not transfinite.     

Concurrency and Refinement in the Unified Modeling Language

This paper defines a formal semantics for a subset of the Unified Modeling Language (UML). It shows how suitable combinations of class, object, state, and sequence diagrams can be associated with patterns of interaction, expressed in the event notation of Communicating Sequential Processes (CSP). The diagram semantics is then extended to give a meaning to complete models – suitable combinations of diagrams – and thus a concurrency semantics for object models written in UML. This model semantics is in turn used to define a theory of refinement, based upon existing notions of data and process refinement.