Abstract families of context-free grammars

An abstract family of grammars (AFG) may be defined as a class of grammars for which the corresponding class of languages forms an abstract family of languages (AFL) as defined by Ginsburg and Greibach. The derivation bounded grammars of Ginsburg and Spanier is an example of an AFG which is properly included in the class of all context-free grammars (also AFG). The main result is that there exist two distinct infinite hierarchies of AFG which exhaust the derivation bounded AFG such that the AFL associated with the kth member of one of these AFG hierarchies is properly included in the AFL associated with the k-lst member of that same hierarchy. Each hierarchy is shown to be strongly incomparable to the other; that is, the first member of each generates some language not generated by a fixed but arbitrary member of the other. We designate these hierarchies as the hierarchies of left and right dominant grammars (languages)     

A Prolog Framework for the Rapid Prototyping of Language Processors with Attribute Grammars

In this paper, we describe PAG (Prototyping with Attribute Grammars), a framework for building Prolog prototypes from specifications based on attribute grammars, which we have developed for supporting rapid prototyping activities in an introductory course on language processors. This framework works for general non-circular attribute grammars with arbitrary underlying context-free grammars, includes a specification language embedded in Prolog that strongly resembles the attribute grammar notations explained in the course cited, and lets students produce comprehensible prototypes from their specifications in a straightforward way.     

On the Expressive Power of OKFDDs

Ordered Decision Diagrams (ODDs) as a means for the representation of Boolean functions are used in many applications in CAD. Depending on the decomposition type, various classes of ODDs have been defined, among them being the Ordered Binary Decision Diagrams (OBDDs), the Ordered Functional Decision Diagrams (OFDDs) and the Ordered Kronecker Functional Decision Diagrams (OKFDDs).Based on a formalization of the concept decomposition type we first investigate all possible decomposition types and prove that already OKFDDs, which result from the application of only three decomposition types, result in the most general class of ODDs. We then show from a (more) theoretical point of view that the generality of OKFDDs is really needed. We prove several exponential gaps between specific classes of ODDs, e.g. between OKFDDs on the one side and OBDDs, OFDDs on the other side. Combining these results it follows that a restriction of the OKFDD concept to subclasses, such as OBDDs and OFDDs as well, results in families of functions which lose their efficient representation.     

On the Expressive Power of Klaim-based Calculi

In this work, we study the expressive power of variants of Klaim, an experimental language with programming primitives for global computing that combines the process algebra approach with the coordination-oriented one. Klaim has proved to be suitable for programming a wide range of distributed applications with agents and code mobility, and has been implemented on the top of a runtime system based on Java. The expressivity of its constructs is tested by distilling from it some (more and more foundational) calculi and studying the encoding of each of the considered languages into a simpler one. An encoding of the asynchronous π-calculus into one of these calculi is also presented.     

On the Expressive Power of Temporal Concurrent Constraint Programming Languages: (invited talk)

The tcc paradigm is a formalism for timed concurrent constraint programming. Several tcc languages differing in their way of expressing infinite behavior have been proposed in the literature. In this work we study the expressive power of some of these languages. In particular, we show that: (1) recursive procedures with parameters can be encoded into parameterless recursive procedures with dynamic scoping, and viceversa. (2) replication can be encoded into parameterless recursive procedures with static scoping, and viceversa. (3) the languages from (1) are strictly more expressive than the languages from (2). Furthermore, we show that behavioral equivalence is undecidable for the languages from (1), but decidable for the languages from (2). The undecidability result holds even if the process variables take values from a fixed finite domain.(Joint work with Mogens Nielsen and Frank D. Valencia)     

On the ω-language Expressive Power of Extended Petri Nets

In this paper, we study the expressive power of several monotonic extensions of Petri nets. We compare the expressive power of Petri nets, Petri nets extended with non-blocking arcs and Petri nets extended with transfer arcs, in terms of ω-languages. We show that the hierarchy of expressive powers of those models is strict. To prove these results, we propose original techniques that rely on well-quasi orderings and monotonicity properties.     

On the equivalence between small-step and big-step abstract machines: a simple application of lightweight fusion

We show how Ohori and Sasano's recent lightweight fusion by fixed-point promotion provides a simple way to prove the equivalence of the two standard styles of specification of abstract machines: (1) in small-step form, as a state-transition function together with a ‘driver loop’, i.e., a function implementing the iteration of this transition function; and (2) in big-step form, as a tail-recursive function that directly maps a given configuration to a final state, if any. The equivalence hinges on our observation that for abstract machines, fusing a small-step specification yields a big-step specification. We illustrate this observation here with a recognizer for Dyck words, the CEK machine, and Krivine's machine with call/cc.The need for such a simple proof is motivated by our current work on small-step abstract machines as obtained by refocusing a function implementing a reduction semantics (a syntactic correspondence), and big-step abstract machines as obtained by CPS-transforming and then defunctionalizing a function implementing a big-step semantics (a functional correspondence).     

On the Expressiveness of Higher Dimensional Automata: (Extended Abstract)

In this paper I compare the expressive power of several models of concurrency based on their ability to represent causal dependence. To this end, I translate these models, in behaviour preserving ways, into the model of higher dimensional automata, which is the most expressive model under investigation. In particular, I propose four different translations of Petri nets, corresponding to the four different computational interpretations of nets found in the literature.I also extend various equivalence relations for concurrent systems to higher dimensional automata. These include the history preserving bisimulation, which is the coarsest equivalence that fully respects branching time, causality and their interplay, as well as the ST-bisimulation, a branching time respecting equivalence that takes causality into account to the extent that it is expressible by actions overlapping in time. Through their embeddings in higher dimensional automata, it is now well-defined whether members of different models of concurrency are equivalent.     

On the existence of delay-insensitive fair arbiters: Trace theory and its limitations

This paper considers the existence and formal specification of delay-insensitive fair arbiters. We show that the exact notion of fairness used is of critical importance because certain common notions are not delay-insensitive when used across independent interfaces. We further show that for the relevant notions of fairness, the existing trace theory of finite traces lacks the expressive power to specify a delay-insensitive fair arbiter (i.e. the specification of such a fair arbiter is also satisfied by an unfair arbiter). Based on this we extend trace theory to include infinite traces, and show by example the importance of including liveness in such a theory. The extended theory is sufficiently expressive to distinguish fair arbiters from unfair ones, and we use it to exhibit a delay-insensitive fair arbiter, thus establishing their existence. In addition our extended theory generalizes the existing trace theory by introducing a composition operator (C) that at once generalizes the existing operators and obviates the composability restrictions used by previous authors. Finally our extended theory introduces wire modules as an abstraction to capture the important role that transmission media properties play in circuit behavior. David L. Black is a graduate student and Ph.D. candidate in the Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA. His research interests include trace theory, temporal logic, and the specification, design and verification of asynchronous circuits. Mr. Black received the B.A. and M.A. degrees in Mathematics along with the B.S.E. (Computer Science and Engineering) degree in 1983 from the University of Pennsylvania, Philadelphia, PA. He also received the M.S. degree in computer science from Carnegie-Mellon University in 1985. Partial support of his graduate studies at Carnegie-Mellon has been provided by a R.K. Mellon fellowship. Mr. Black is also a member of Phi Beta Kappa, Tau Beta Pi, Eta Kappa Nu and Pi Mu Epsilon.     

On the use of a formal requirements engineering language: The Generalized Railroad Crossing Problem

In this paper, we report on the use of theAlbert II requirements specification language through the handling of the Generalized Railroad Crossing case study. This formal language is based on an ontology of concepts used for capturing requirements inherent in real-time, distributed systems. Because of itsnaturalness, the language supports a direct mapping of customers’ informal needs onto formal statements, without having to introduce artificial elements. The language is founded on a formal framework (real-time temporal logic) which supports the reasoning process of the analyst during the elaboration of the specification. Such support for the reasoning is illustrated in the context of a goal-oriented approach adopted for the elaboration of the case study.     

Discovering the functional mesh: On the methods of evolutionary psychology

The aim of this paper is to clarify and critically assess the methods of evolutionary psychology, and offer a sketch of an alternative methodology. My thesis is threefold. (1) The methods of inquiry unique to evolutionary psychology rest upon the claim that the discovery of theadaptive functions of ancestral psychological capacities leads to the discovery of thepsychological functions of those ancestral capacities. (2) But this claim is false; in fact, just the opposite is true. We first must discover the psychological functions of our psychological capacities in order to discover their adaptive functions. Hence the methods distinctive of evolutionary psychology are idle in our search for the mechanisms of the mind. (3) There are good reasons for preferring an alternative to the methods of evolutionary psychology, an alternative that aims to discover the functions of our psychological capacities by appeal to the concept of awhole psychology.     

On the Logic of Theory Change: Contraction without Recovery

The postulate of Recovery, among the six postulates for theory contraction, formulated and studied by Alchourrón, Gärdenfors and Makinson is the one that has provoked most controversy. In this article we construct withdrawal functions that do not satisfy Recovery, but try to preserve minimal change, and relate these withdrawal functions with the AGM contraction functions.     

On the mathematical theory of living systems II: The interplay between mathematics and system biology

This paper aims at showing how the so-called mathematical kinetic theory for active particles can be properly developed to propose a new system biology approach. The investigation begins with an analysis of complexity in biological systems, continues with reviewing a general methodology to reduce complexity and furnishes the mathematical tools to describe the time evolution of such systems by capturing all their features.     

On the lattice of specifications: Applications to a specification methodology

In this paper we investigate the lattice properties of the natural ordering between specifications, which expresses that a specification expresses a stronger requirement than another specification. The lattice-like structure that we uncover is used as a basis for a specification methodology.     

The positive and negative implications of anonymity in Internet social interactions: “On the Internet, Nobody Knows You’re a Dog”

The growth of the Internet at a means of communication has sparked the interest of researchers in several fields (e.g. communication, social psychology, industrial-organizational psychology) to investigate the issues surrounding the expression of different social behaviors in this unique social context. Of special interest to researchers is the increased importance that anonymity seems to play in computer-mediated communication (CMC). This paper reviews the literature related to the issues of anonymity within the social context, particularly in CMC, demonstrating the usefulness of established social psychological theory to explain behavior in CMC and discussing the evolution of the current theoretical explanations in explaining the effects of anonymity in social behavior in CMC environments. Several suggestions for future research are proposed in an attempt to provide researchers with new avenues to investigate how anonymity can play both positive and negative roles in CMC.     

Computerization as a means of cultural change: On the relations between information theories and the idea of an information society

Since World War II the concept of Information has received several new definitions. Information can be understood as knowledge in general, as theoretical, formalized knowledge in general or as knowledge related to specific domains or specific representational forms. Because of these mutually inconsistent concepts the common traits are to be found in a perspective transcendent to those theories. The central cultural changes, it is argued, take place on the level of the societal knowledge infrastructure, evolving from the knowledge infrastructure of the industrial societies as a long-term secularization process, resulting in new forms for representation and manipulation of knowledge. The process is seen as rooted in changes of the primary domains for knowledge extraction and in a change in the human relations to the languages in which we interpret the relations to nature.