Current Trends in Theoretical Computer Science

The following sections are included:

• Preface

• CONTENTS

The following sections are included:

• Introductory Remarks

The following sections are included:

• What is Computational Geometry?

• Publishing in Computational Geometry

• Shaving Logs
  • Why don't we leave the log alone?
  • What makes the log disappear?
  • Also dishonest logs can have honest descendents

• The 4-th Computational Geometry Symposium

• Two Weeks Worth of Teaching

• Two Small Results
  • Non-Obtuse Triangulations
  • Stabbing Triangles

• Computational Geometry Research in Japan

• Meetings in 1991

The following sections are included:

• Introductory Remarks

The potential role of algebraic specifications is discussed including the historical development, interaction of theory and applications, and its present role and future aims within Computer Science.

The following sections are included:

• Preliminaries

• Equations

• The structuring principle

• Initial-algebra semantics

• Parameterization

• Correctness

• Bibliographic notes

In this guest column, I would like to present some very informal and personal recollections of the exciting early days of ADJ. This time was very important for me personally, and I also think was significant for the field of algebraic specification. These recollections are highly personal, which necessarily means that they are also highly biased, and probably inaccurate in some respects; but perhaps this will also make the result more amusing to read…

Based on a questionnaire for information about applications of algebraic specifications published in the Bulletin of the EATCS the results are presented in three parts

Part I: Overview of Algebraic Specification Languages

Part II: Overview of Environments and Tools for Algebraic Specifications

Part III: Overview of Algebraic Specifications of Software Systems

The following sections are included:

• The system

• Comments on a practical application

• References

The following sections are included:

• Introduction

• Some real problems and some non-problems

• Conclusion

• Acknowledgements

A short review of the present version of some main ESF-concepts within the ESF-project (EUREKA Software Factory) is given and a link with algebraic concepts of module specifications is established.

The notion of schemes in brain theory, neural engineering and robotics is proposed to be liked with algebraic specifications of modules and modular systems.

Concepts for transformations and implementations of specifications including compatibility requirements which have been developed in the 80's are discussed on a general level.

As one specific example implementation concepts for parameterized specifications within the initial algebraic approach are considered and their compatibility results concerning parameter passing are discussed in more detail. Finally some brief remarks on implementation and transformation of processes and projection specifications are given.

Several new results concerning compatibility of implementations for parameterized specifications within the initial algebraic approach are presented. The implementation concepts which are based on different combinations of synthesis, restriction and identification steps are investigated concerning closure under composition and compatibility with parameter passing. In the case of implementations including a synthesis step extended correctness criteria are presented to overcome the known lack of compositionality. Finally we discuss the extension problem for implementations without synthesis leading to implementations with synthesis.

The concepts of amalgamation and extension are of fundamental importance for various kinds of equational and behavioural algebraic specifications. They are studied in the unified framework of a specification logic and in the corresponding category of generalized morphisms. This leads to interesting characterizations via pushouts and to the concepts of generalized amalgamation and generalized extension which are new even in the special case of equational algebraic specifications.

In Object Oriented Programming the powerful mechanism of inheritance allows the definition of classes starting from variables and methods of another class previously defined. Inheritance can be viewed as a relation between classes, which suggests how classes can be arranged in hierarchies.

In order to distinguish between code sharing, which is related to implementational aspects, and functional specialization, which is connected to the external behavior of objects, we propose an algebraic specification based formalism, by which one can specify the behavior of a class and state when a class is to be considered subtype or inherits another one.

An axiomatic treatment of restriction constructions for models of abstract algebraic specifications is presented which generalizes the well-known restriction concept for algebraic varieties based on equational algebraic specifications to models of a specification logic. A general uniqueness result for restriction shows that both standard constructions for restriction coincide where the first is defined as intersection while the second is given by image factorization of the counit of free constructions.

The specification and design of a Very Large Scale Integrated circuit (VLSI) involves issues similar to those arising in the design of large software systems. In recent years many concepts have evolved within the Algebraic Specification frameworks to model, primarily, issues arising in the context of software systems development. In this note we begin the task of exploring the applicability of these concepts to the VLSI design process.

This survey makes the following points: (1) overloaded OSA can be developed with minimal assumptions on signatures and algebras; (2) it is useful to distinguish between strong and weak overloading; in the latter, an expression can have at most one value in a given algebra, although it may have several distinct parses; (3) strong overloading is needed for certain important applications of OSA, including dynamic binding in object oriented programming, and operations on data with multiple representations; (4) it seems much more difficult to establish certain basic mathematical properties of universal OSA than of overloaded OSA; for example, it is not known whether universal OSA satisfies the Birkhoff variety theorem; and (5) sort constraints and retracts greatly increase the expressive and computational power of OSA.

The following sections are included:

• Introductory Remarks

I felt honored and uncertain when Grzegorsz Rozenberg, the president of EATCS, proposed that I write a continuing column on logic in computer science in this Bulletin. Writing essays wasn't my favorite subject in high school. After some hesitation, I decided to give it a try. I'll need all the help I can get from you: criticism, comments, queries, suggestions, etc…

Infinite games are widely used in mathematical logic [2, 8, 12]. In particular, infinite games proved to be a useful tool in dealing with the monadic second-order theories of infinite strings and infinite trees [3, 4, 7]. Recently [1, 15, 13], infinite games were used in connection to concurrent computational processes that do not necessarily terminate. For example, an operating system may be seen as playing a game “against” the disruptive forces of users. The classical question of the existence of winning strategies turns out to be of importance to practice. Here we attempt to explain basics of infinite game theory…

Please refer to full text

Please refer to full text

The following sections are included:

• Preface

• Another computation model

• Static algebras

• Transition rules

• Example 1: A stack machine

• Static, dynamic and external functions

• Example 2: A Turing machine

• Example 3: The strcpy function

• Sequential and nonsequential evolving algebras

• Acknowledgement

• References

Please refer to full text

This is the written version of a talk given at the C.I.R.M. Workshop on Logic in Computer Science at Marseille, France in June, 1988. Its purpose is to argue that there is a close connection between the theory of computation and the geometric side of topos theory. We begin with a brief outline of the history and basic concepts of topos theory.

The author and a questioner engage in a dialogue on methods for proving lower complexity bounds for decidable logical theories. The author describes a technique analogous to interpreting theories, a method which has been used to prove undecidability. The questioner is somewhat direct, but they part on good terms.

The way to specify a programming language has been a topic of heated debate for some decades and at present there is no consensus on how this is best done. Real languages are almost always specified informally; nevertheless, precision is often enough lacking that more formal approaches could benefit both programmers and language implementors. My purpose in this column is to look at a few of these formal approaches in hope of establishing some distinctions or at least stirring some discussion…

This is a survey of some current issues regarding the declarative semantics of logic programming. The key topics covered are negation-as-failure, the completion semantics as compared with the minimal model semantics, the semantics of built-in predicates (such as numeric evaluation), and constraint logic programming.

An overview of linear logic is given, including an extensive bibliography and a simple example of the close relationship between linear logic and computation.

The following sections are included:

• Introductory Remarks

The systematic study of computational complexity theory was initiated in the early sixties and during the following twenty-five years complexity theory has developed into one of the central and most active research areas of computer science. It has grown into a rich and exciting mathematical theory whose development is motivated and guided by computer science needs and technological advances. At the same time, it is clear that complexity theory, dealing with the quantitative laws of computation and reasoning, is concerned with issues and problems of direct interest to many other disciplines as well. It is quite likely that in the overall impact of computer science on our thinking, complexity theory will be recognized as one of the most influential intellectual contributions…

The following sections are included:

• Introduction

• Sparse Complete Sets for NP

• Conclusion

• References

The following sections are included:

• Introduction

• Census Functions and Collapsing Hierarchies

• Space Bounded Hierarchies

• Boolean, Query, and Polynomial Hierarchies

• References

The following sections are included:

• About Relativization

• Relativization of Space Bounded Computations

• Relativized Separation of Space Bounded Computations

• Proof of Results

• References

In this column, we show how a variety of interesting results in theory of computation all follow from a simple observation about II₂-complete sets of total machines. We easily derive:

a) representation-independent independence results,

b) non-recursive succinctness relations between different representations of languages,

c) the existence of incomplete languages in various complexity classes

In a 1956 letter, Gödel asked von Neumann about the computational complexity of an NP complete problem. In this column, we review the historic setting of this period, discuss Gödel's amazing letter and why von Neumann did not solve the P =? NP problem.

The purpose of this column is to informally describe some of the themes and paradigms of structural complexity theory.

In the spring of 1989, Seinosuke Toda of the University of Electro-Communications in Tokyo, Japan, proved that the polynomial hierarchy is contained in P^PP [To-89]. In this Structural Complexity Column, we will briefly review Toda's result, and explore how it relates to other topics of interest in computer science. In particular, we will introduce the reader to

The Counting Hierarchy: a hierarchy of complexity classes contained in PSPACE and containing the Polynomial Hierarchy.

Threshold Circuits: circuits constructed of MAJORITY gates; this notion of circuit is being studied not only by complexity theoreticians, but also by researchers in an active subfield of AI studying “neural networks”.

Along the way, we'll review the important notion of an operator on a complexity class.

It has been shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible computations. Furthermore, the IP = PSPACE result reveals some very interesting and unsuspected properties of mathematical proofs.

In this column we define the width of a proof in a formal system and show that it is an intuitively satisfying and robust definition. Then, using the IP = PSPACE result, it is seen that the width of a proof (as opposed to the length) determines how quickly one can give overwhelming evidence that a theorem is provable without showing the full proof.

Ever since Valiant and Vazirani [VV86] showed that there exists a random reduction from SAT to USAT, the complexity of USAT has been cited as “USAT is complete for D^P under randomized reductions.” However, the definition of the randomized reduction was never quite satisfying because the probability of a “correct” reduction can approach zero as the length of the formula increases. The discrepancy between the Valiant-Vazirani definition and the earlier Adleman-Manders [AM77] definition has been noted previously [Joh85]. This column reflects on recent results about the complexity of USAT and of D^P which shed a new light on the meaning of completeness under randomized reductions. For example, it is pointed out that, under randomized reductions, USAT is complete for P^{SAT[log n]} as well. These results also show that the non-robustness of D^P creates many difficulties in defining a randomized reduction which gives a meaningful notion of completeness.

The following sections are included:

• Introduction

• Some complexity classes of functions

• Some Results

• On the difficulty of inverting functions in PF

• Can nondeterminism be guided?

• Comments and Acknowledgements

• References

Defined in 1979 by Valiant, #P is the class of functions that count the number of “solutions” of NP problems. During the 1980s, #P was shown to possess many closure properties. Quite recently, a theory has been developed that structurally characterizes the conditions under which #P possesses other natural closure properties. This article surveys the study of the closure properties of #P.

The following sections are included:

• The Twice-Told Tale

• The Current State of Mathematics

• A Revisionist's Tale

• A Turning Point

• References

The following sections are included:

• Introductory Remarks

The problem proposed by Gauss of characterizing the code of a simple crossing closed curve (SCCC, for short) can be considered a formal language question. We define three related infinite languages. Two of them are regular; the type of the third is an open problem.

The following sections are included:

• The basic technique

• Quasi-solutions

• Further applications of the basic technique

• Reference

It is an often stated rule of thumb that everything concerning finite automata is decidable. However, there are some exceptions to this rule. Moreover, the decidability of equivalence between two deterministic finite multitape automata has been a celebrated open problem. The problem dates back to 1959, to the classical paper of Rabin and Scott, [11], where multitape automata were introduced and where it was also shown that, in contrast to one-tape automata, nondeterministic multitape automata are more powerful than deterministic ones…

No other puzzle game played on a board has maintained its popularity through centuries as firmly as solitaire. The origin of the game is unknown, although according to a story (Is there any respected game whose history does not contain legends ?) it was invented by a French nobleman confined to the Bastille. For understandable reasons the man had plenty of spare time, which he started to kill by moving stones on a board drawn in the ground. In any case it is sure that solitaire was known in 1716 as the famous German mathematician Gottfried Leibniz mentiones the game in a letter…

This column is of a rather specific nature. It concentrates on the discussion of the impact of a particular problem on the theory of formal languages. This impact provides an excellent example of what science is at its best: not only are consequences of a problem or a discovery deep, but also unpredictable…

The following sections are included:

• Morphisms applied in the way of a fugue

• Generalized number systems

• Bounded delay

• A sample proof

• Immigration

• Acknowledgements

• References

Several attempts have been made to find a suitable model for parallel processing. Cellular automata [9], Lindenmayer systems [18], systolic trellis automata [3], Russian parallel [4] and Indian parallel [4] grammars are some examples of such models based on formal language and automata theories. In these devices the parallelism is local. Symbols are rewritten independently of each other. No major cooperation between the parallel processes occurs, although, for instance, in L-systems with interactions some minor cooperation appears…

Some dense phenomena in discrete systems are studied. We show how graphs and hypergraphs form a dense order analogous to that of rational numbers. The concept gives a link between graph theory and language theory. Known results are surveyed and a few new results on hypergraphs are presented together with open problems.

The following sections are included:

• ABOUT THE EDITORS