Automata, Languages and Programming

Dependencies are certain sentences of first-order logic that are of special interest for database theory and practice. There has been quite a bit of research in the last decade in investigating dependencies. A selective overview of this research is presented. In particular, the focus is on the implication problem for dependencies, and on issues related to the universal relation model.

Presented in these pages are personal observations concerning the effect that Very Large Scale Integrated circuit technology (VLSI) has had on the Theoretical Computer Science field and community, together with some guesses as to why this technological advance has had so much more profound an effect on the Community than have had numerous earlier technological advances. The tale spun includes some sociology, some technology, and some history — as well as some theoretical material, mostly as illustration.

The concept of tuple sequence is introduced in order to investigate structure connected with relational model implementation. Well-known problems like decomposition and duplicates are addressed for tuple sequences. The lexicographical ordering of tuple sequences is studied via the notion of index (dependency). Certain properties of index families are shown, and two algorithmiques questions related to indexes considered. Also, a sound and complete set of inference rules for indexes is exhibited. Finally, indexes and functional dependencies in combination are studied.

We introduce the notion of a p-generic set. P-generic sets automatically have all properties which can be enforced by usual diagonalizations over polynomial time computable sets and functions. We prove that there are recursive — in fact exponential time computable — p-generic sets. The existence of p-generic sets in NP is shown to be oracle dependent, even under the assumption that P ≠ NP.

We introduce recursively defined processes and regular processes, both in presence and absence of communication. It is shown that both classes are process algebras. As an example of recursively defined processes, Bag and Stack are discussed in detail. It is shown that Bag cannot be recursively defined without merge. We introduce fixed point algebras which have useful applications in several proofs.

In this paper, we first discuss the various algebraic approaches to exception handling specification. We show that none of them is completely satisfactory, and we explain why the algebraic specification of exception handling (error introduction, error propagation and error recovery) must not be made using only equations, but also "declarations". We present an approach allowing all forms of error handling, and at the same time keeping specifications well-structured and easily understandable.

Let a partial deterministic finite automaton be a DFA in which each state need not have a transition edge for each letter of the alphabet. We demonstrate that the minimal partial DFA for the set of all subwords of a given word w, |w| > 2, has at most 2|w| − 2 states and 3|w| − 4 transition edges, independently of the alphabet size. We give an algorithm to build this minimal partial DFA from the input w on-line in linear time.

We study the difficulty of solving instances of a new family of sliding block puzzles called SEPARATIONTM. Each puzzle in the family consists of an arrangement in the plane of n rectilinear wooden blocks, n > 0. The aim is to discover a sequence of rectilinear moves which when carried out will separate each piece to infinity. If there is such a sequence of moves we say the puzzle or arrangement is separable and if each piece is moved only once we say it is one-separable. Furthermore if it is one-separable with all moves being in the same direction we say it is iso-separable.We prove:(1)There is an O(n log n) time algorithm to decide whether or not a puzzle is iso-separable, where the blocks have a total of n edges.(2)There is an O(n log2n) time algorithm to decide whether or not a puzzle is one-separable.(3)It is decidable whether or not a puzzle is separable.(4)Deciding separability is NP-hard.(5)There are puzzles which require time exponential in the number of edges to separate them.

A linear time algorithm for determining the maximal number of collision-free transmissions in an arbitrary series-parallel network is developed. The method operates by a recursive contraction of the network to a single edge; during this contraction process, information is retained concerning each of the subnetworks which has been eliminated. This efficient solution contrasts with the known NP-completeness of the problem for general networks.

Searching a square in a word may be implemented in time proportional to the length of the word on a randomm access machine provided the alphabet is fixed.

This paper proposes a way of relating domain-theoretic and algebraic interpretations of data types. It is different from Smyth, Plotkin, and Lehmann's T-algebra approach, and in particular the notion of homomorphism between higher-order algebras is not restricted in the same way, so that the usual initiality theorems of algebraic semantics, including one for inequational varieties, hold. Domain algebras are defined in terms of concepts from elementary category theory using Lambek's connection between cartesian closed categories and the typed λ-calculus. To this end axioms and inference rules for a theory of domain categories are given. Models of these are the standard categories of domains, such as Scott's information systems and Berry and Curien's sequential algorithms on concrete data structures. The set of axioms and inference rules are discussed and compared to the PP_λ-logic of the LCF-system.

We investigate the family of matrix languages (studied by A. Salomaa) and the family of matrix languages of index less than K (studied by J. Beauquier and G. Paun), for each K ≥ 1. We solve an open problem : all these families are principal rational cones. Moreover, we establish a relation between their respective generators.

In the Prolog language, Horn clauses of first-order logic are regarded as programs, and the resolution procedure is used as an interpreter.In this paper, we present the formalism of Horn oriented equational clauses (Horn clauses with a rewrite rule as the head part, and a list of equations as the body part). We show that such a formalism can be interpreted as a logic language with built-in equality, and that a procedure, based on clausal superposition, can be used as an interpreter.We define, the operational, model-theoretic and fixpoint semantics of the language, and prove their equivalence.Then we point out the advantages of such a programming language:embodying Prolog,mixing functional and relational features,handling the equality relationLastly, we present experiments performed with an implemented interpreter.

We are interested in infinitary languages recognized by a pushdown automaton. We, then, give theorems of characterization of such closed, central, normal or perfect languages (considering a number of hypothesis of continuity in computations of the automaton, for last three classes). Besides, it is proved that, given the same hypothesis, the largest central (respectively normal, perfect, language included in an algebraic infinitary language, remains algebraic.

We give a partial order semantics to (pure) CCS via a translation into Petri nets and prove, that the interleaved behaviour of the resulting nets is equivalent to Milner's semantics. We show that a large class of CCS programs can be represented by finite nets and that this is impossible for the whole CCS.

Consider a network of two communicating finite state machines which exchange messages over two one-directional, unbounded channels, and assume that each machine receives the messages from its input channel based on some fixed (partial) priority relation. We address the problem of whether the communication of such a network is deadlock-free and bounded. We show that the problem is undecidable if the two machines exchange two types of messages. The problem is also undecidable if the two machines exchange three types of messages, and one of the channels is known to be bounded. However, if the two machines exchange two (or less) types of messages, and one channel is known to be bounded, then the problem becomes decidable. The problem is also decidable if one machine sends one type of message and the second machine sends two (or less) types of messages; the problem becomes undecidable if the second machine sends three types of messages. The problem is also decidable if the message priority relation is empty. We also address the problem of whether there is a message priority relation such that the priority network behaves like a FIFO network. We show that the problem is undecidable in general, and present some special cases for which the problem becomes decidable.

We propose, a translation method of finite terms of CCS into formulas of a modal language representing their class of observational congruence. For this purpose, we define a modal language and a function associating with any finite term of CCS a formula of the language, satisfied by the term. Furthermore, this function is such that two terms are congruent if and only if the corresponding formulas are equivalent. The translation method consists in associating with operations on terms (action,+) operations on the corresponding formulas.This work is a first step towards the definition of a modal language with modalities expressing both possibility and inevitability and which is compatible with observational congruence.

We shall consider the communication complexity introduced by Papadimitriou and Sipser [4]. The hierarchy of this communication complexity is proved for both deterministic and nondeterministic models. The communication complexity hierarchy for k-way communication is also established.

In this paper we present some space/time efficient Turing machine algorithms for recognizing some subclasses of DCFL's. In particular, we show that the finite minimal stacking and “simple” strict restricted (a subclass of strict restricted) deterministic pushdown automata (FMS-DPDA's SSR-DPDA's, respectively) can be simulated by offline Turing machines simultaneously in space S(n) and time n2/S(n) for any tape function S(n) satisfying log n ≤ S(n) ≤ n which is constructable in n2/S(n) time. Related techniques can be used to give interesting characterizations of 2-head 2-way finite automata, both deterministic and nondeterministic. In particular we show that a 2-head 2-way deterministic finite automataton is equivalent to a simple type of 2-way deterministic checking stack automaton. This is in contrast to a result which shows that 2-way nondeterministic checking stack automata are equivalent to nondeterministic linear bounded automata. We also show that a language L is accepted by a 2k-head two-way nondetermistic finite automaton if and only if it is accepted by a k-head two-way nondeterministic pushdown automaton which makes at most one reversal on its stack.

In this paper we have introduced the concept of cl-regular expression, proposed the axiom system & for cl-regular expressions, and proved the soundness and completeness of the system &. The system & will be a base for algebraic studies on cl-regular sets. On the other hand, the system & coincides with the Salomm's axiom system if we restrict the objects to the regular sets of finite strings. In this sense, our axiom system is a natural extension of Salomaa's axiom system to allow cl-regular set including infinite strings.The referee kindly informed the authors that an axiom system for ω-regular expressions has earlier been introduced by K. Wagner [6]. But the use of closed regular expressions in this paper leads to our axiom system &, a more elegant and natural one than the use of ω-regular expressions.

We show that three-element codes have some special properties which do not hold even for four-element codes. Firstly, for each three-element code A, if u and v are words in pref(xAθ) π pref(yAθ), with x, y ∈ A, x ≠ y, then one of them is a prefix of the other, i.e., among the words which can be covered in two different ways from left to right there exists a unique maximal (possibly infinite) element. Secondly, each three-element code has a bounded delay in at least one direction.

This paper gives a performance analysis of one variant of Shamir's attack on the basic Merkle-Hellman knapsack cryptosystem, which we call Algorithm S. Let $$R = \frac{{\# plain text bits}}{{maximum \# cipher text bits}}$$ denote the rate at which a knapsack cryptosystem transmits information, and let n denote the number of items in a knapsack, i.e. the block size of plaintext. We show that for any fixed R Algorithm S runs to completion in time polynomial in n on all knapsacks with rate R_o>-R. We show that it successfully breaks at least the fraction $$1 - \frac{{c_R }}{n}$$ of such knapsack cryptosystems as n → ∞, where c_R is a constant depending on R.

The concept of presortedness and its use in sorting are studied. Natural ways to measure presortedness are given and some general properties necessary for a measure are proposed. A concept of a sorting algorithm optimal with respect to a measure of presortedness is defined, and examples of such algorithms are given. An insertion sort is shown to be optimal with respect to three natural measures. The problem of finding an optimal algorithm for an arbitrary measure is studied and partial results are proven.

According to VLSI theory, [logn, √n] is the range of computation times for which there may exist an AT2-optimal multiplier of n-bit integers. Such networks were previously known for the time range [Ω(log2n), 0(√n)]; in this paper we settle this theoretical question, by exhibiting a-class of AT2-optimal multipliers with computation times [Ω(logn), 0(n1/2)]. Our designs are based on the DFT on a Fermat ring, whose elements are represented in a redundant radix-4 form to ensure 0(1) addition time.

We study in this paper the operational and greatest fixpoint semantics of infinite computations in logic programming. We show their equivalence in the case of fair derivations, and generalize to infinite computations some important results about finite ones.

The problem of finding the coarsest partition of a set S with respect to another partition of S and one or more functions on S has several applications, one of which is the state minimization of finite state automata. In 1971 Hopcroft presented an algorithm to solve the many function coarsest partition problem for sets of n elements in O(n log n) time and O(n) space. Aho, Hopcroft, and Ullman later presented an algorithm that solves the special case of this problem for only one function. Both these algorithms use a negative strategy that repeatedly refines the original partition until a solution is found. We present a new algorithm to solve the single function coarsest partition problem in O(n) time and space using a different, constructive approach.

Ehrenfeucht, Lee et Rozenberg ont montré que la complexité des facteurs des D0L langages (et donc des mots infinis engendrés par morphismes itérés) était majorée par cn2 (resp. cn log n, cn) suivant que le morphisme est quelconque, croissant ou uniforme. Nous introduisons une classe intermédiaire dont la complexité est majorée par cn log log n. De plus, nous montrons que tout mot infini engendré par morphisme a une complexité en O(n2), O(n log n), O(n log log n), O(n) ou O(1) suivant la nature du morphisme.

On montre que la puissance des automates boustrophédon reste inchangée pour divers modes de reconnaissance. On en déduit certaines propriétés des parties rationnelles du semi-groupe de Birget et du monoide inversif libre.

In this paper we consider a fundamental problem of resource allocation in a distributed network. Each user's demands for resources may change dynamically and the processors speeds can vary dynamically. Let v be the maximum number of users competing for a particular resource at any time instant. Let k be the maximum number of resources that a user is willing to get, at any time instant. This problem was previously formulated in [Lynch, 1980]. It has application (1) to two-phase locking in databases (2) to generalized dining philosophers, and (3) to the implementation of a novel extension of the CSP language, called Social-CSP and to many other applications to concurrent programming.Informally we say that an algorithm for this problem is real time if its response time is upper bounded by a function which does not depend on any global measure of the system of processes and resources, except k and v. [Reif, Spirakis, 1982b] gave the first known real time algorithms to the problem, with (mean) response time of o(vk). This response time may be too long, however, in applications where k has a large value.In this paper we provide new algorithms whose response time is polynomial to v and k. Our most efficient new algorithm has expected response time o(vk). Moreover, our constant factors appear to be small enough for practical applications.Unlike our previous probabilistic algorithms of [Reif, Spirakis, 1982b], we do not use random delays as means of avoiding process starvation and of achieving probabilistic fairness. Instead, our new algorithm utilizes a method of probabilistic bidding, to resolve contention of users for resources. This technique is essential in our achievement of polynomial response time.We furthermore prove that our solution is optimal with respect to the average response to a user's request. In particular we provide matching lower bounds for any distributed algorithm for resource allocation, and these bounds are within a constant factor of the response time of our own algorithms.We also provide a suboptimal algorithm which is useful for improving the throughput rate of resource allocation in systems where the majority of users is willing to get only a few resources. This suboptimal algorithm does use random waits combined with probabilistic bidding. These techniques employ limited parallelism within each process, together with the probabilistic bidding. (This limited parallelism is useful in achieving optimal response time, though we would still get polynomial response time without limited parallelism.)

A design for a hardware interface that implements CSP-like communication primitives is presented. The design is based on a bus scheme that allows processes to “eavesdrop” on messages not directly addressed to them. A temporal logic specification is given for the network and an outline of a verification proof is sketched.

All steps described in the preceding section for fixed m are certainly covered by the rather crude bound of $$O(m(n^{5 + \varepsilon } + n^3 (log|f|)^{2 + \varepsilon } ))$$ bit operations. For a factor p of degree $$k \leqslant \frac{n}{2}$$ this bound applies for m=2,4,... until some m with m/2<k≤m is reached. The sum of the corresponding time bounds is therefore $$O(k(n^{5 + \varepsilon } + n^3 (log|f|)^{2 + \varepsilon } ))$$ . Further factors are found in the very same way, dealing with f/p, etc. There is at most one factor of degree k>n/2 (possibly f itself), thus the final time bound $$O(n^{6 + \varepsilon } + n^4 (log|f|)^{2 + \varepsilon } ))$$ is obtained.It should be observed that the distinctions between the real and complex case in Lemma 6.1 and in Lemma 6.2 nicely match such that in both cases log B∼6mn+2(m+n) log|f|. Due to the estimation (6.1) sometimes shortcuts in the reduction process may be possible. As soon as |b_m*|2 becomes greater than 3·22m-1|f|2, bm can be eliminated from the reduction, etc.It is conceivable that further (mainly theoretical) improvements of our algorithm are possible, for instance by exploiting fast matrix multiplication, or by iterating the block reduction technique.

The propositional mu-calculus is a propositional logic of programs which incorporates a least fixpoint operator and subsumes the Propositional Dynamic Logic of Fischer and Ladner, the infinite looping construct of Streett, and the Game Logic of Parikh. We give an elementary time decision procedure, using a reduction to the emptiness problem for automata on infinite trees. A small model theorem is obtained as a corollary.

We present a data structure based on AVL-trees which allows to perform an insertion or a deletion in time O(log d) where'd is the distance of the position searched for from the finger which points to the end of the file. Moving a finger costs O(log d). This result demonstrates the power of the oldest basic data structure, the AVL-tree. A special case of interest is an efficient implementation of searchable priority queues such that Deletemin requires only constant time.

A BLAH machine is any memory device that can be simulated in real-time by a multitape Turing machine and such that a multiBLAH machine can real-time simulate a pushdown store. A multiBLAH machine consists of a finite control connected to an input terminal and an output terminal and one or more copies of the BLAH memory unit. It is shown that a (k+1)-BLAH machine is more powerful in real-time than a k-BLAH machine, for each k. Thus the hierarchies, within the real-time definable computations, are proper and smooth, that is, adding a device always increases power. It also turns out that all real-time hierarchy results in this vein are simple corollaries of a single root: the real-time hierarchy of multipushdown store machines. As examples of such new results we mention that in real-time, k+1 tape-units with a fast rewind square are more powerful than k such units; that (k+1)-head tape-units with fast rewind squares are more powerful than k-head tape-units with fast rewind squares; that (k+1)-dequeue machines are more powerful than k-dequeue machines; and that (k+1)-concatenable-dequeue machines are more powerful than k-concatenable-dequeue machines.

The notion of an I/O interface for optical digital (write-once) disks is introduced that is quite different from earlier research in this area. The purpose of an I/O interface is to allow existing operating systems and application programs that use magnetic disks to use optical disks instead, with minimum difficulty. The interface is especially geared to applications that are not update-intensive or that require access to previous versions of records. We define what it means for an I/O interface to be disk-efficient. We demonstrate a disk-efficient interface and show that its I/O performance in many cases is optimum, up to a constant factor, among all disk-efficient interfaces. The basis of the interface is a data structure we call offset trees, which stores information about intervals with dynamically changing coordinates. Since this complexity model is based on practical concerns, these theoretical results translate nicely into an efficient implementation.