A family of sequence operations (rs-operations), based on pattern matching and including most of the “natural” operations on sequences, is introduced. In order to apply rs-operations to calculus-like query languages, a logic about sequences (SL) is defined by converting rs-operations to special predicates. To illustrate the applicability of our concepts to database queries, rs-operations and SL are used in an algebra and a calculus, respectively, over an extended relational data model containing sequences.

The concept of a tuple sequence is introduced in order to investigate structure connected with relational model implementation. Analogs are presented for the relational operations of projection, join, and selection, and the decomposition problem for tuple sequences is considered. The lexicographical ordering of tuple sequences is studied via the notion of (lexicographic) index. A sound and complete set of inference rules for indexes is exhibited, and two algorithmic questions related to indexes examined. Finally, indexes and functional dependencies in combination are studied.

The notion ofsort setis introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways to enhance the efficiency of an implemented database. A characterization of when order dependency implies the existence of sort sets in a database is presented, along with several corollaries concerning complexity, Armstrong relations, and cliques of certain graphs. Sort-set dependencies are then introduced. A (finite) sound and complete set of inference rules for sort-set dependencies is presented, as well as a proof that there is no such set for functional and sort-set dependencies taken together. Deciding logical implication for sort-set dependencies is proved to be polynomial, but if functional dependencies are included the problem is co-NP-complete. Each set of sort-set and functional dependencies is shown to have an Armstrong relation. A natural generalization of Armstrong relation, here calledseparator, is given and then used to study the relationship between order and sort-set dependencies.

A record-based, algebraically-oriented model is introduced for describing data for “object histories” (with computation), such as checking accounts, credit card accounts, taxes, schedules, and so on. The model consists of sequences of computation tuples defined by a computation-tuple sequence scheme (CSS). The CSS has three major features (in addition to input data): computation (involving previous computation tuples), “uniform” constraints (whose satisfaction by a computation-tuple sequence u implies satisfaction by every interval of u ), and specific sequences with which to start the valid computation-tuple sequences. A special type of CSS, called “local,” is singled out for its relative simplicity in maintaining the validity of a computation-tuple sequence. A necessary and sufficient condition for a CSS to be equivalent to at least one local CSS is given. Finally, the notion of “local bisimulatability” is introduced for regarding two CSS as conveying the same information, and two results on local bisimulatability in connection with local CSS are established.

The notion of "sort set" is introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways to enhance the efficiency of an implemented database. A characterization of when order dependency implies the existence of sort sets in a database is presented, along with several corollaries concerning conplexlty, Armstrong relations and cliques of certain graphs.Sort-set dependencies are then introduced A (finite) sound and complete set of inference rules for sort-set deoendencies is presented, but there is no such set for functional and sort-set dependencies taken together. Deciding logical immplication for sort-set dependencies is proved to be polynomial, but if functional dependencies are included the problem is co-NP complete. Each set of sort-set and functional dependencies is shown to have an Armstrong relation A natural generalization of Armstrong relation, here called "separator," is given and then used to study the relationship between order and sort-set dependencies.

A functional-dependency (FD-) family Is defined here as the family of all instances satisfying a set of functional dependencies These families are studied with respect to projection, join, and decomposition and their connection with generating families and generators Typical results obtained are (0 a charactenzauon for when the projection of an FD-family is an FD-family; 00 a charactenzauon for when the join of two FD-famihes is an FD-famdy, (m) a necessary and sufficient condition for an F D-famdy to be decomposable; and 0v) that every domam-infmlte FD-family has a generatorOne surpnsmg conclusion of this study is that there seems to be a considerable difference between the case in which each domain is relatively large with respect to the number of domains considered and the case m wluch some of the domains are relatively small.

A conceptually simple scheme is exhibited for specifying syntactically correct programs of declarative, block-structured programming languages. The method is then demonstrated on a selected subset of PL/1. The scheme itself is based on grammar forms, a concept recently introduced to provide a unified treatment of structurally related grammars. The form grammar provides the BNF equivalent for the syntax. The interpretations of the grammar form are constructed dynamically during the scanning of the input program and map the form grammar into a context-free grammar satisfying the constraints of the given programming language.

Let F be an arbitrary context-free grammar form and $\mathcal{G}(F)$ the family of grammars defined by F. For each grammar G in $\mathcal{G}(F)$, the derivation complexity function $\Phi _G$, on the language of G, is defined for each word x as the number of steps in a minimal G-derivation of x. It is shown that derivations may always be speeded up by any constant factor n, in the sense that for each positive integer n, an equivalent grammar $G'$ in $\mathcal{G}(F)$ can be found so that $\Phi _{G'} (x) \leqq | x | / n$ for all large words $x,| x |$ denoting the length of x.

Grammar forms are compared for their efficiency in representing languages, as measured by the sizes (i.e. total number of symbols, number of variable occurrences, number of productions, and number of distinct variables) of interpretation grammars. For every regular set, right- and left-linear forms are essentially equal in efficiency. Any form for the regular sets provides, at most, polynomial improvement over right-linear form. Moreover, any polynomial improvement is attained by some such form, at least on certain languages. Greater improvement for some languages is possible using forms expressing larger classes of languages than the regular sets. However, there are some languages for which no improvement over right-linear form is possible. While a similar set of results holds for forms expressing exactly the linear languages, only linear improvement can occur for forms expressing all the context-free languages.

The definition of “grammar form” introduced in [CG] makes it possible to state and prove results about various types of grammars in a uniform way. Among questions naturally formalizable in this framework are many about the complexity or efficiency of grammars of different kinds. Grammar forms provide a reasonable way of considering the totality of other forms we might use, and so answering the question with both upper and lower bound results.

A solution is presented for the following problem: Determine a procedure that produces, for each full trio L of context-free languages (more generally, each trio of r.e. languages), a family of context-free (phrase structure) grammars which (a) defines L, (b) is simple enough for practical and theoretical purposes, and (c) in most cases is a subfamily of a well-known family of context-free (phrase structure) grammars for L if such a well-known family exists. (A full trio (trio) is defined to be a family of languages closed under homomorphism (ε-free homomorphism), inverse homomorphism, and intersection with regular sets.) The key notion in the paper is that of a grammar schema. With each grammar schema there is associated a family of interpretations. In turn, each interpretation of a grammar schema gives rise to a phrase structure grammar. Given a full trio (trio) L of context-free (r.e.) languages, one constructs a grammar schema whose interpretations (ε-limited interpretations) then give rise to the desired family of grammars for L.

Families of acceptors, called SS-AFA, are introduced in which the storage structure is of a very general form. For example, SS-AFA include ordinary AFA and all known multitape AFA, as well as families of acceptors whose storage structure is an n-dimensional array, a tree, or a linked structure. It is shown that from the point of view of languages defined, SS-AFA are equivalent to ordinary AFA.

The purpose of this paper is to show that a number of well-known families have property (*). In particular, we prove that the family of context-free languages does indeed have this property. In addition, we show that several familiar subfamilies of the context-free languages, such as the one-counter languages, have property (*). Finally, we show that there are families satisfying (*) which are not subfamilies of the context-free languages, for we prove that any family generated from one-letter languages has property (*), thereby extending a result of [17].

Device representations, via multitape AFA (abstract families of acceptors), are given for the families of languages which result from applying the wedge (A) m)d the substitution operations to AFL (abstract families of languages).In particular, if ~ and ~2 are multitape AFA (i.e.certain families of multistorage tape acceptors), then 5)~ A ~2 is defined as the family of multitape acceptors which results when the tapes of ~ and ~2 are coalesced, with the ~-tapes preceding those in ~2 .It is shown that the smallest full AFL containing 2(~) A 2 (~D2) = {L~ N L2 ILi in2 (~Di) } is ,12 (~ h~:).For each multitape AFAr, aset ~.v of "nested" multitape acceptors is defined.It is shown that if ~ and ~2 are single-tape AFA, then the family of languages obtained from (~ A ~2) N is the family of langnages obtained by substituting the AFL defined by ~2 into the AFL defined by ~D~ .

@ a* and the ratio of the number of words in L of length less than n to n goes to 1 as [equation], then [equation] does not contain all recursively enumerable languages.

It is shown that if the family of languages accepted by a closed class of two-way balloon automata is closed under length-preserving homomorphism, then this family is an abstract family of languages (AFL) closed under intersection and e-free substitution.It is then proved that the family of languages accepted by the closed class of (nonerasing) (deterministic) stack acceptors is such a family.

A device is presented which has its memory organized as a linear list, a type of storage equivalent to having two pushdown stores. Attention is then focused on the nondeterministic automaton (called an lsa ) which results when the input is read one-way and the device operates in real-time. The set of words (called a language ) accepted by an lsa is extensively studied. In particular, several characterizations and closure properties of languages are given.

Compilation consists of two parts, recognition and translation. A mathematical model is presented which embodies salient features of many modern compiling techniques. The model, called the stack automaton, has the desirable feature of being deterministic in nature. This deterministic device is generalized to a nondeterministic device (nondeterministic stack automaton) and particular instances of this more general device are noted. Sets accepted by nondeterministic stack automata are recursive. Each set accepted by a deterministic linear bounded automaton is accepted by some nonerasing stack automaton. Each context-sensitive language is accepted by some (deterministic) stack automaton.

A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation, the latter. Several solvability questions are also considered.

Four principal results about ambiguity in languages (i.e., context free languages) are proved. It is first shown that the problem of determining whether an arbitrary language is inherently ambiguous is recursively unsolvable. Then a decision procedure is presented for determining whether an arbitrary bounded grammar is ambiguous. Next, a necessary and sufficient algebraic condition is given for a bounded language to be inherently ambiguous. Finally, it is shown that no language contained in w 1 * w 2 *, each w 1 a word, is inherently ambiguous.

Various elementary operations are studied to find whether they preserve on ambiguity and inherent ambiguity of language (“language” means “context-free language”) The following results are established: If L is an unambiguous language and S is a generalized sequential machine, then (a) S ( L ) is an unambiguous language if S is one-to-one on L , and (b) S -1 ( L ) is an unambiguous language. Inherent ambiguity is preserved by every generalized sequential machine which is one-to-one on the set of all words. The product (either left or right) of a language and a word preserves both unambiguity and inherent ambiguity. Neither unambiguity nor inherent ambiguity is preserved by any of the following language preserving operations: (a) one state complete sequential machine; (b) product by a two-element set; (c) Init ( L ) = [ u ≠ dur in L for some v ]; (d) Subw ( L ) = [ w ≠ durr in L for some u , v ].

Several devices with two input lines and one output line are introduced. These devices are viewed as transformations which operate on pairs of (ALGOL-like) languages. Among the results proved are the following: (i) a pair consisting of a language and a regular set is transformed into a language; (ii) let ( V, W ) be a pair consisting of a language and a regular set. Then the set of those words w 1 , for which there exists a word w 2 in V so that ( w 1 , w 2 ) is mapped into W , is a language.

Each of the following three problems is shown to be recursively solvable for arbitrary regular sets U and V. (1) Does there exist a complete sequential machine which maps U into V? (2) Does there exist a generalized sequential machine which maps U i~to V so that the image of U is infinite if U is infinite?(3) Does there exist a complete seque~tial machine which maps U onto V?

article Free Access Share on Some Recursively Unsolvable Problems in ALGOL-Like Languages Authors: Seymour Ginsburg System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile , Gene F. Rose System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 10Issue 1pp 29–47https://doi.org/10.1145/321150.321153Published:01 January 1963Publication History 26citation387DownloadsMetricsTotal Citations26Total Downloads387Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

To better understand the syntax of problem-oriented languages, the equational form used in defining ALGOL [1] was recently abstracted [6].On varying the coefficients in the abstract equational form two families of languages arose.[A language is viewed as a set of strings, called words, of symbols from a finite, fixed alphabet.]The two types of languages, called definable and sequentially definable, were then investigated and a number of properties discovered.In particular, it was shown that the definable languages were identical to the type-two phrase structure languages introduced by Chomsky [4].The present paper deals with operations T (on languages) which preserve definability ~nd frequently sequential definability.All operations considered have the additional property of preserving regularity [7]--the interest in regular sets stemming from the fact that they have been considered as "finite state languages" [3].Two basic results are proved.The first (Theorem 2.1) permits derivation of (sequential) definability-preserving operations from other (sequential) definability-preserving operations.The second (Theorem 3.1) asserts that a sequential machine always changes a definable set into a definable set (but not necessarily a sequentially definable set into a sequentially definable set).Using these two results, a large number of specific operations-many occurring in data processing--arc shown to preserve definability and, depending on the operation, sequential definability.In addition to the two main results there occur in appendices A and B necessary conditions for a set to be sequentiMly definable and definable respectively.The former is the first known necessary condition for sequentially definable sets which differs from those for definable sets.It is anticipated that many of the operations considered here will be useful in later studies of problem oriented languages.

The following results on the quotient of context-free languages (CFL) are shown: (1) It is reeursively unsolvable to determine for arbitrary CFL whether the quotient of one by another is a CFL.(2) If either set is regular and the other is a CFL, then the quotient is a CFL.

article Free Access Share on Two Families of Languages Related to ALGOL Authors: Seymour Ginsburg System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile , H. Gordon Rice Computer Sciences Corp., Palos Verdes, Calif and System Development Corporation, Santa Monica, California Computer Sciences Corp., Palos Verdes, Calif and System Development Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 9Issue 3pp 350–371https://doi.org/10.1145/321127.321132Published:01 July 1962Publication History 225citation961DownloadsMetricsTotal Citations225Total Downloads961Last 12 Months65Last 6 weeks10 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Numerous physical situations related to data processing are shown to be modeled by a mathematical entity called a quasi-machine. The situations described include 1) single inputs producing multiple outputs, 2) machines yielding no outputs upon insertion of certain inputs, 3) the retention of the last n outputs only, 4) ``erase left'' on tape, 5) different input routines doing the same work, and 6) certain types of asynchronous switching circuits. The first five may be modeled by quasi-machines with a special property, such quasi-machines being called abstract machines.

article Free AccessSets of Tapes Accepted by Different Types of Automata Author: Seymour Ginsburg System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 8Issue 1Jan. 1961 pp 81–86https://doi.org/10.1145/321052.321056Published:01 January 1961Publication History 7citation322DownloadsMetricsTotal Citations7Total Downloads322Last 12 Months15Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

article Free AccessCompatibility of States in Input-Independent Machines Author: Seymour Ginsburg System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 8Issue 3pp 400–403https://doi.org/10.1145/321075.321083Published:01 July 1961Publication History 6citation278DownloadsMetricsTotal Citations6Total Downloads278Last 12 Months18Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

article Free Access Share on Connective Properties Preserved in Minimal State Machines Author: Seymour Ginsburg System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 7Issue 4Oct. 1960 pp 311–325https://doi.org/10.1145/321043.321045Published:01 October 1960Publication History 7citation313DownloadsMetricsTotal Citations7Total Downloads313Last 12 Months18Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

article Free Access Share on On the Reduction of Superfluous States in a Sequential Machine Author: Seymour Ginsburg The National Cash Register Company, Hawthorne, California The National Cash Register Company, Hawthorne, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 6Issue 201 April 1959pp 259–282https://doi.org/10.1145/320964.320983Published:01 April 1959Publication History 26citation399DownloadsMetricsTotal Citations26Total Downloads399Last 12 Months24Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A method is presented which always yields a minimal state sequential machine satisfying a prescribed finite set of input-output sequences. An application is made to the case where a given sequential machine is to be reduced, by the merging technique, to a machine having the smallest number of states possible. Numerous examples are given.

A technique is presented for reducing an arbitrary machine S as much as possible to a machine T which can do everything (from the input-output point of view) that S can do. Since the technique is always applicable, it is more powerful (although more cumbersome) than the well-known merging technique. Several examples are given.

A technique is presented which yields a minimal-state machine satisfying a given set of behavioral specifications. The machine is constructed in the same manner as has commonly been done in the past in synthesizing a ``primitive flow table.'' This contribution consists, not in describing a new method of synthesizing machines, but in showing that a particular instance of an established method yields a minimal-state machine. It is shown that the basic synthesis technique may be slightly modified so as to be applicable to obtaining a minimal-state machine which has the stability condition desired when working with uncloked circuits.

The problem considered here is to obtain estimates of the length of the smallest experiment (on a machine) which is independent of the unknown initial state and which allows us, by observing the outputs, to distinguish the terminal state.The estimates obtained depend, of course, on the assumptions placed on the machine.In general, the bounds derived are slightly less than n ~, where n is the number of distinguishable states in the machine.For no really general class of machines is a best bound known. P r e l i m i n a r y Results