STOC

Section 1 of this paper presents the basic mathematical definitions for our work. Section 2 defines the notion of a weighted phrase-structure grammar over either a semiring or zero monoid coefficient structure. The notion of canonical derivations (from ...

This is the introductory paper in a series devoted to a general algebraic theory of “recursive definitions” and “recursive languages”. In this paper we present the fundamental concepts and theorems concerning the basic structure (basic syntax), the ...

We define a class of program schemata arising from the subrecursive programming language Loop. In this preliminary report on Loop schemata we show how to assign functional expressions to these schemata (as one aspect of the problem of assigning meaning ...

Computational Complexity is concerned with how difficult, under some measure of difficulty, it is to evaluate certain functions or classes of functions. Most of the work in this area, however, deals with models of computation quite unlike a stored ...

This paper deals with three aspects of algebraic complexity. The first section is concerned with lower bounds on the number of operations required to compute several functions. Several theorems are presented and their proofs sketched. The second section ...

In this paper we present a substantially general theory of parenthesis-free notations for finite plane trees. We obtain stronger one-to-oneness results, including a characterization of one-to-oneness for a large class of notations, and a quite general ...

The notion of the graphical representation of a “canonical derivation” is extended to semi-thue systems; the graphs are called “derivation structures.” Derivation structures are distinguished from phrase structures and generative grammars are ...

In this paper, we will essentially present three results in tree automata. Two of these are concerned with certain open problems posed by Rounds [1] and Martin and Vere [3], and the third one is related to the result of Peters and Ritchie [4].

First we ...

The question as to the correct block exit strategy, retention or deletion, is resolved by formally comparing the contour model and the stack model, each of which implements one of the strategies, to the copy rule, a formal definition of block ...

The problem of parallel computation of local operations using five differently organized parallel processing machines (the SASD, SAPD, PASD, PAMD, and PAPD computers) is investigated. It is shown that for a special class of local operations, called ...

We give a definition of one-counter languages. We show that the smallest full AFL containing this family is principal with full generator D'@@@@ @@@@, the semi-Dyck language on two letters. We then give without the proof, which shall be published ...

A study is made of conditions on a language L which ensure that the smallest intersection-closed full AFL containing L (written @@@@ @@@@(L)) does or does not contain all recursively enumerable languages. For example, it is shown that if L = {aⁿ_i/i @@@@ ...

Absolutely parallel grammars are defined and it is shown that the family of languages generated is equal to the family of languages generated by two-way deterministic finite-state transducers. Furthermore it is shown that this family forms a full AFL [4]...

This paper continues the study of the classes of data graphs which are implementable in a random access memory using “relative addressing” and “relocatable realization”, which was initiated in [1]. A new characterization of the class of rooted (=...

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology. Here “reduced” means, roughly speaking, ...

We consider methods of modifying LR(k) parsers [1] while preserving the ability of that parsing method to detect errors at the earliest possible point on the input. Two transformations are developed, and the methods of Korenjak [2] and DeRemer [3] are ...

Recently Hext and Roberts have attempted to refine Domolki's parsing algorithm to include limited context checking. This paper links their effort to Lynch's overlap resolvable grammars, which are here extended to include ε-rules. Both Lynch's and Hext ...

An algorithm is described, whose input is a context-free grammar G and whose output is, if G fulfils a set of conditions, a decision table for a deterministic bottom up parser yielding the syntactic structure of the terminal sentences that belong to L (...

In [1] various problems are solved about the possibility of mapping regular sets into or onto other regular sets by means of a complete sequential machine or a generalized sequential machine under various restraints. One problem in this class has ...

In the present paper, an algebraic structure theory of stochastic machines is developed which contains both Bacon's theory [1] and Hartmanis' theory for deterministic machines [5] as special cases. Although the present theory is patterned after both ...

The purpose of this paper is to give a model for the study of quantitative problems about formal translations from one programming language into another, as well as derive some initial results about the speed of programs produced by translations. The ...

A classification of all the computable functions is given in terms of subrecursive programming languages. These classes are those which also arise from the relation “primitive recursive in.” By distinguishing between honest and dishonest classes the ...

This paper studies possible extensions of the concept of complexity class of recursive functions to partial recursive functions. Many of the well-known results for total complexity classes are shown to have corresponding, though not exactly identical, ...