STOC

This paper gives an overview of subrecursive hierarchy theory as it relates to computational complexity and applies some of the concepts to questions about the size of programs in subrecursive programming languages. The purpose is three-fold, to reveal ...

After a brief discussion of historical matters in §1, twenty-seven predicates of formal grammers are introduced in §2. The next two sections discuss recursively enumerable predicates and nonrecursively enumerable predicates, respectively. These results ...

The study of Computational Complexity began with the investigation of Turing machine computations with limits on the amounts of tape or time which could be used. Latter a set of general axioms for measures of resource limiting was presented and this ...

It is proven that complexity classes of abstract measures of complexity need not be recursively enumerable. However, the complement of each class is r.e.

Properties of effective enumerations of complexity classes are studied. For any measure there is ...

We consider here the problem of building transfinite hierarchies of computable functions on the basis of their difficulty of computation. Previous hierarchies of functions through the constructive ordinals have had two major problems, each apparently ...

Let f be a partial recursive function defined in terms of other functions g₁,...,g_n such that f converges if and only if some well defined assertions about the convergency of g₁,...,g_n hold: then we can find a total function (depending on the number of ...

A data graph is obtained from a data structure by masking out the specific data items at the nodes of the structure and concentrating only on the linkages in the structure. Structural uniformities in data graphs can often be exploited to facilitate and ...

The study of computational complexity is continued under the additional requirement that the Turing machines operate in real time. The work reported here is motivated by that of Rabin [R] which asks implicitly about the computational power of n tape vs ...

Our main result, theorem 2, gives a bound on the storage required for a Turing machine to simulate certain time-bounded pushdown machines. The theorem is a generalization of the result appearing in [3] stating that any context-free language can be ...

Two of the more recently published systems for the efficient parsing of subclasses of deterministic, context-free languages are the backwards-deterministic, (or unambiguous, as they were originally called) simple precedence languages due to Wirth and ...

An incremental language processor is one that accepts as input a sequence of substrings of the source language and maps them independently onto fragments in some object code. The ordered sequence of these object code fragments are then either compiled, ...

Complexity classes of formal languages defined by time- and tape-bounded Turing acceptors are studied with the aim of showing sufficient conditions for these classes to be AFLs and to be principal AFLs.

This paper treats the closure of families of formal languages under operators which may be viewed as substitution into a particular language. A language L over alphabet {a₁,...,a_n} induces an n-place operator on languages by substitution of the n ...

In this paper we study some applications and generalizations of the yield theorem: the yield of a recognizable set of trees (dendrolanguage) is an indexed language [1]. Standard results on context-free languages can be obtained quickly using this ...

We define a general class of tree-manipulating systems that includes many of the special cases from logic, linguistics, and automata theory. Systems possessing what we call the “Church-Rosser property” are appropriate for evaluation or translation ...

Several topics of theoretical and practical importance to the field of translator writing systems are presented in this paper. These are

(1). implementation of generalized syntax-directed transduction (GSDT) on a finite-state tree transducer;

(2). ...

We consider a program schema that models straight line intermediate level code. A complete set of equivalence preserving transformations on programs is found for the case in which programs are equivalent if and only if their output functions are ...

Landin's SECD Machine does not completely compute certain expressions of the λ-calculus and so is modified by the addition of an output component and a unique name counter. This modified machine is proven to correctly implement the λ-calculus.

In this work we show that it is possible to formalize all properties regularly observed in (deterministic and non-deterministic) algorithms in second-order predicate calculus.

Moreover, we show that for any given algorithm it suffices to know how to ...

A special purpose theorem prover for establishing the validity of expressions over integer variables was developed as part of a program verifier. It is built around a powerful system for manipulating and simplifying integer expressions.

The predicate elimination strategy is a complete resolution proof strategy for multi-predicate formulas. Essentially, the procedure focuses on one of the predicate symbols P, and attempts to deduce clauses independent of P by means of resolution in ...

This paper proposes the foundations for a systematic study of the translation of recursive function definitions into flow charts (often called the removal of recursions). Several notions of translation are presented. Emphasis is placed on translation ...

The purpose of this paper is meant to be three-fold. First it will introduce the reader to the concepts of Probabilistic Languages and Probabilistic Grammars. Second, it indicates that previous definitions of probabilistic finite automaton have always ...

A method for the description of the hierarchical structure of two-dimensional pictures is proposed. The model is called picture-processing grammar. It can be regarded as an extension of phrase-structure grammars to the two-dimensional case. A picture ...

It is the aim of the present study to establish links between the structure of a given (finite) prefixcode and that of its syntactic monoid, using automata theory as a tool.

We recall that the Dyck language on the alphabet of 2n letters X = {x₁,...,x_n,x₁,...,x_n} is the equivalence class of the empty word 1 ε X@@@@ modulo the Thue congruence generated on X@@@@ by the 2n relations x_ix_i = x_ix_i = 1 i ε {1,...,n}.

Indeed for all ...

(1) If every set in @@@@ is a subset of a^* and the empty word belongs to one of them, then 7(@@@@)=7 (@@@@). One consequence is that 7(L) is always principal for L ≤ a^*. (2) On the other hand, there is a language L ≤ a^*b^* such that 7(L) is not ...