Organizing programs without classes

All organizational functions carried out by classes can be accomplished in a simple and natural way by object inheritance in classless languages, with no need for special mechanisms. A single model—dividing types into prototypes and traits—supports sharing of behavior and extending or replacing representations. A natural extension, dynamic object inheritance, can model behavioral modes. Object inheritance can also be used to provide structured name spaces for well-known objects. Classless languages can even express class-based encapsulation. These stylized uses of object inheritance become instantly recognizable idioms, and extend the repertory of organizing principles to cover a wider range of programs.This work has been generously supported by National Science Foundation Presidential Young Investigator Grant # CCR-8657631, and by Sun Microsystems, IBM, Apple Computer, Cray Laboratories, Tandem Computers, NCR, Texas Instruments, and DEC.     

A remark about a substitution property

S. A. Greibach proved in Chains of full AFL's a useful property concerning the substitution of full semi-AFL's. We prove here that this property remains true when the families of languages under considerations are assumed only to be full trios, i.e., closure under union is not required.     

Regular Tree Languages as an Abstract Domain in Program Specialisation

On-line partial evaluation algorithms include a generalisation step, which is needed to ensure termination. In partial evaluation of logic and functional programs, the usual generalisation operation is the most specific generalisation (msg) of expressions. This can cause loss of information, which is especially serious in programs whose computations first build some internal data structure that is then used to control a subsequent phase of execution—a common pattern of computation. If the size of the intermediate data is unbounded at partial evaluation time then the msg will lose almost all information about its structure. Hence subsequent phases of computation cannot be effectively specialised.In this paper the problem is tackled by introducing regular tree languages into a partial evaluation algorithm. A regular tree language is a set of terms defined by tree automata or tree grammars. In the algorithm, regular tree approximations of sets of terms encountered during partial evaluation are constructed. The critical point is that when generalisation is performed, the upper bound on regular tree languages can be combined with the msg, thus preserving recursive information about term structure. This approach also allows the specialisation of programs with respect to goals whose arguments range over regular tree languages.The algorithm is presented as an instance of Leuschel's framework for abstract specialisation of logic programs. This provides a generic algorithm parameterised by an abstract domain—regular trees in this case. The correctness requirements from his framework are established. The extension of the algorithm to propagate regular approximations of answers as well as calls is also presented, increasing the amount of specialisation that can be obtained. Finally a technique for increasing precision based on wrapper functions is introduced.     

On tolerable and desirable behaviors in supervisory control of discrete event systems

We formulate and solve a new supervisory control problem for discrete event systems. The objective is to design a logical controller—or supervisor—such that the discrete event system satisfies a given set of requirements that involve event ordering. The controller must deal with a limited amount of controllability in the form of uncontrollable events. Our problem formulation considers that the requirements for the behavior (i.e., set of traces) of the controlled system are specified in terms of a desired behavior and a larger tolerated behavior. Due to the uncontrollable events, one may wish to tolerate behavior that sometimes exceeds the ideal desired behavior if overall this results in achieving more of the desired behavior. The general solution of our problem is completely characterized. The nonblocking solution is also analyzed in detail. This solution requires the study of a new class of controllable languages. Several results are proved about this class of languages. Algorithms to compute certain languages of interest within this class are also presented.Research supported in part by the National Science Foundation under grants ECS-8707671, ECS-9057967, and ECS-9008947.     

Concept of the Risk Evaluation Possibilities in Complex Systems

For systems of the form potentially dangerous object—means and measures of protection—dangerous and harmful factors, consideration was given to the concept of multiple-parameter modeling and the possibilities of (fuzzy) risk evaluation which was intended for determining the asymptotic safety (risk) indices in the presence of fuzzy and/or incomplete source data about the system due to the cost or time constraints. This approach can be characterized as a fusion of the concepts of absolute safety and acceptable risk.     

Marr's three levels: A re-evaluation

Marr's account of the analysis of complex information-processing tasks as having three levels — the levels of computational theory, representation and algorithm, and hardware implementation — is reconsidered. I argue that the notion of level here runs together two distinctive sort of explanatory shifts — that of grain and that of contextual function. I then offer a revision of the account which avoids this problem, and suggest how this might play a role in the practice of theory evaluation.     

Graph theoretic closure properties of the family of boundary NLC graph languages

Summary Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs) which rewrite single nodes only and establish connections between the embedded graph and the neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels, languages of unlabeled graphs). Boundary NLC (BNLC) grammars are NLC grammars with the property that whenever — in a graph already generated — two nodes may be rewritten, then these nodes are not adjacent. The graph languages generated by this type of grammars are called BNLC languages. The present paper continues the investigations of basic properties of BNLC grammars and languages where the central question is the following: If L is a BNLC language and P is a graph theoretic property, is the set of all graphs from L satisfying P again a BNLC language? We demonstrate that the class of BNLC languages is very stable in the sense that for almost all properties we consider the resulting languages are BNLC. In particular, the above question gets an affirmative answer, if the property P is: being k-colorable, being connected, having a subgraph homeomorphic to a given graph, and being nonplanar.This research was carried out during the second author's stay at the Rijksuniversiteit Leiden, The Netherlands     

Well quasi-orders and regular languages

An extension of Myhill's theorem of automata theory, due to Ehrenfeucht et al. [4] shows that a subsetX of a semigroupsS is recognizable if and only ifX is closed with respect to a monotone well quasi-order onS. In this paper we prove that a similar extension of Nerode's theorem is not possible by showing that there exist non-regular languages on a binary alphabet which are closed with respect to a right-monotone well quasi-order. We give then some additional conditions under which a setX S closed with respect to a right-monotone well quasi-order becomes recognizable. We prove the following main proposition: A subsetX ofS is recognizable if and only ifX is closed with respect to two well quasi-orders<=₁ and<=₂ which are right-monotone and left-monotone, respectively. Some corollaries and applications are given. Moreover, we consider the family of all languages which are closed with respect to a right-monotone well quasi-order on a finitely generated free monoid. We prove that is closed under rational operations, intersection, inverse morphisms and direct non-erasing morphisms. This implies that is closed under faithful rational transductions. Finally we prove that the languages in satisfy a suitable pumping lemma and that contains languages which are not recursively enumerable.     

Chains of full AFL's

If a full AFL is not closed under substitution, then ô , the result of substituting members of into, is not substitution closed and hence generates an infinite hierarchy of full AFL's. If ₁ and ₂ are two incomparable full AFL's, then the least full AFL containing ₁ and ₂ is not substitution closed. In particular, the substitution closure of any full AFL properly contained in the context-free languages is itself properly contained in the context-free languages. If any set of languages generates the context-free languages, one of its members must do so. The substitution closure of the one-way stack languages is properly contained in the nested stack languages. For eachn, there is a class of full context-free AFL's whose partial ordering under inclusion is isomorphic to the natural partial ordering onn-tuples of positive integers.This paper was completed while the author was in the Division of Engineering and Applied Physics of Harvard University. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under contracts F-1962870C0023 and F-1962868C0029, and by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR Grant No. AF-AFOSR-1203-67A and the Division of Engineering and Applied Physics of Harvard University.     

Random Constraint Satisfaction: A More Accurate Picture

In the last few years there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Quite intriguingly, experimental results with various models for generating random CSP instances suggest that the probability of such problems having a solution exhibits a threshold–like behavior. In this spirit, some preliminary theoretical work has been done in analyzing these models asymptotically, i.e., as the number of variables grows. In this paper we prove that, contrary to beliefs based on experimental evidence, the models commonly used for generating random CSP instances do not have an asymptotic threshold. In particular, we prove that asymptotically almost all instances they generate are overconstrained, suffering from trivial, local inconsistencies. To complement this result we present an alternative, single–parameter model for generating random CSP instances and prove that, unlike current models, it exhibits non–trivial asymptotic behavior. Moreover, for this new model we derive explicit bounds for the narrow region within which the probability of having a solution changes dramatically.     

On Automating Diagrammatic Proofs of Arithmetic Arguments

Theorems in automated theorem proving are usually proved by formal logical proofs. However, there is a subset of problems which humans can prove by the use of geometric operations on diagrams, so called diagrammatic proofs. Insight is often more clearly perceived in these proofs than in the corresponding algebraic proofs; they capture an intuitive notion of truthfulness that humans find easy to see and understand. We are investigating and automating such diagrammatic reasoning about mathematical theorems. Concrete, rather than general diagrams are used to prove particular concrete instances of the universally quantified theorem. The diagrammatic proof is captured by the use of geometric operations on the diagram. These operations are the inference steps of the proof. An abstracted schematic proof of the universally quantified theorem is induced from these proof instances. The constructive -rule provides the mathematical basis for this step from schematic proofs to theoremhood. In this way we avoid the difficulty of treating a general case in a diagram. One method of confirming that the abstraction of the schematic proof from the proof instances is sound is proving the correctness of schematic proofs in the meta-theory of diagrams. These ideas have been implemented in the system, called Diamond, which is presented here.     

The complexity of computing maximal word functions

Maximal word functions occur in data retrieval applications and have connections with ranking problems, which in turn were first investigated in relation to data compression [21]. By the maximal word function of a languageL ^*, we mean the problem of finding, on inputx, the lexicographically largest word belonging toL that is smaller than or equal tox.In this paper we present a parallel algorithm for computing maximal word functions for languages recognized by one-way nondeterministic auxiliary pushdown automata (and hence for the class of context-free languages).This paper is a continuation of a stream of research focusing on the problem of identifying properties others than membership which are easily computable for certain classes of languages. For a survey, see [24].     

NC1: The automata-theoretic viewpoint

Concepts from the algebraic theory of finite automata are carried over to the program-over-monoid setting which underlies Barrington's algebraic characterization of the complexity classNC ¹. Sets of languages accepted by polynomial-length programs over finite monoids drawn from a given monoid variety V emerge as fundamental language classes: as V ranges over monoid varieties these classes capture and indeed refine the usual bounded-depth circuit parametrization of nonuniformNC ¹ subclasses. Here it is shown that any two separable such language classes can be separated by a regular language. Basic properties of these language classes are exhibited. New conditions are given under which distinct varieties lead to equal or to distinct language classes, thus sharpening our knowledge of the internal structure of non-uniformNC ¹. The paper concludes with the statement of a conjecture whose proof would refine and then resolve most open questions about this internal structure.     

Replaceability and computational equivalence for monotone boolean functions

Summary Replacement rules have played an important role in the study of monotone boolean function complexity. In this paper, notions of replaceability and computational equivalence are formulated in an abstract algebraic setting, and examined in detail for finite distributive lattices — the appropriate algebraic context for monotone boolean functions. It is shown that when computing an element f of a finite distributive lattice D, the elements of D partition into classes of computationally equivalent elements, and define a quotient of D in which all intervals of the form [t f, t f] are boolean. This quotient is an abstract simplicial complex with respect to ordering by replaceability. Other results include generalisations and extensions of known theorems concerning replacement rules for monotone boolean networks. Possible applications of computational equivalence in developing upper and lower bounds on monotone boolean function complexity are indicated, and new directions of research both abstract mathematical and computational, are suggested.     

On the usefulness of bifaithful rational cones

Roughly, a faithful (resp. bifaithful) rational transduction is a non deterministic finite state mapping that does not decrease (resp. alter) the length of words by very much. We introduce the notion of stronglyf-saturated language:L is stronglyf-saturated if and only if for any languageL, from which we can obtainL by faithful rational transduction, for any languageL, image ofL by a faithful rational transduction, there exists a bifaithful rational transduction such thatL is the image ofL . We prove that no quasirational language and no language in the substitution closed rational cone generated by bounded languages is stronglyf-saturated. Conversely, we establish that a language such as , very low in the hierarchy of algebraic languages, is stronglyf-saturated thus is not a quasirational language. We also establish that any commutative quasi rational language over two letters is rational.     

Games with Uniqueness Properties

For two-player games of perfect information such as Checkers, Chess, and Go we introduce uniqueness properties. A game position has a uniqueness property if a winning strategy—should one exist—is forced to be unique. Depending on the way that winning strategy is forced, a uniqueness property is classified as weak, strong, or global. We prove that any reasonable two-player game G is extendable to a game G ^* with the strong uniqueness property for both players, so that, e.g., QBF remains PSPACE-complete under this reduction. For global uniqueness, we introduce a simple game over Boolean formulas with this property, and prove that any reasonable two-player game with the global uniqueness property is reducible to it. We show that the class of languages that reduce to globally unique games equals Niedermeier and Rossmaniths unambiguous alternation class UAP, which is in an interesting region between FewP and SPP.     

Hierarchies of modal and temporal logics with reference pointers

We introduce and study hierarchies of extensions of the propositional modal and temporal languages with pairs of new syntactic devices: point of reference-reference pointer which enable semantic references to be made within a formula. We propose three different but equivalent semantics for the extended languages, discuss and compare their expressiveness. The languages with reference pointers are shown to have great expressive power (especially when their frugal syntax is taken into account), perspicuous semantics, and simple deductive systems. For instance, Kamp's and Stavi's temporal operators, as well as nominals (names, clock variables), are definable in them. Universal validity in these languages is proved undecidable. The basic modal and temporal logics with reference pointers are uniformly axiomatized and a strong completeness theorem is proved for them and extended to some classes of their extensions.     

A logic covering undefinedness in program proofs

Summary Recursive definition often results in partial functions; iteration gives rise to programs which may fail to terminate for some imputs. Proofs about such functions or programs should be conducted in logical systems which reflect the possibility of undefined values. This paper provides an axiomatization of such a logic together with examples of its use.     

A multiprocessor working as a Fault-Tolerant cellular automaton

A memory-coupled multiprocessor—well suited to bit-wise operation—can be utilized to operate as a 1024 items cellular processing unit. Each processor is working on 32 bits and 32 such processors are combined to a multiprocessor. The information is stored in vertical direction, as it is defined and described in earlier papers [1] on vertical processing. The two-dimensional array (32 times 32 bits) is composed of the 32 bit-machine-words of the coupled processors on the one hand and of 32 processors in nearest-neighbour-topology on the other hand. The bit-wise cellular operation at one of the 1024 points is realized by the program of the processor—possibly assisted by appropriate microprogam sequences.Dedicated to Professor Willard L. Miranker on the occasion of his 60th birthday     

Graph expressions and graph rewritings

We define an algebraic structure for the set of finite graphs, a notion of graph expression for defining them, and a complete set of equational rules for manipulating graph expressions. (By agraph we mean an oriented hypergraph, the hyperedges of which are labeled with symbols from a fixed finite ranked alphabet and that is equipped with a finite sequence of distinguished vertices). The notion of a context-free graph grammar is introduced (based on the substitution of a graph for a hyperedge in a graph). The notion of an equational set of graphs follows in a standard way from the algebraic structure. As in the case of context-free languages, a set of graphs is contextfree iff it is equational. By working at the level of expressions, we derive from the algebraic formalism a notion of graph rewriting which is as powerful as the usual one (based on a categorical approach) introduced by Ehrig, Pfender, and Schneider.This work has been supported by the PRC Mathématiques et Informatique. Reprints can be requested from B. Courcelle by electronic mail at the following address (UUCP network): mcvax!inria!geocub!courcell.