Search For:

Displaying 1-24 out of 24 total
Foreword
Found in: 23rd Annual Symposium on Foundations of Computer Science
By Michael J. Fischer,Michael J. Fischer,Michael J. Fischer,Michael J. Fischer,Seymour Ginsburg,Seymour Ginsburg,Seymour Ginsburg,Seymour Ginsburg,David G. Kirkpatrick,David G. Kirkpatrick,David G. Kirkpatrick,David G. Kirkpatrick,Richard E. Ladner,Richard E. Ladner,Richard E. Ladner,Richard E. Ladner,Gary L. Miller,Gary L. Miller,Gary L. Miller,Gary L. Miller,Nicholas Pippenger,Nicholas Pippenger,Nicholas Pippenger,Nicholas Pippenger,Dana Scott,Dana Scott,Dana Scott,Dana Scott,Leslie G. Valiant,Leslie G. Valiant,Leslie G. Valiant,Leslie G. Valiant,Mihalis Yannakakis,Mihalis Yannakakis,Mihalis Yannakakis,Mihalis Yannakakis,F. Frances Yao,F. Frances Yao,F. Frances Yao,F. Frances Yao
Issue Date:November 1982
pp. iii
No summary available.
   
Two-way balloon automata and AFL
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Seymour Ginsburg, John Hopcroft
Issue Date:October 1968
pp. 292-297
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 AFL closed under intersection and ε-free substitution. It is then proved that the fami...
 
Derivation-bounded languages
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Seymour Ginsburg, Edwin H. Spanier
Issue Date:October 1968
pp. 306-314
A derivation in a phrase-structure grammar is said to be k-bounded if each word in the derivation contains at most k occurrences of nonterminals. A set L is said to be derivation bounded if there exists a phrase-structure grammar G and a positive integer k...
 
One-way stack automata — Extended abstract
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Seymour Ginsburg, Sheila A. Greibach, Michael A. Harrison
Issue Date:October 1966
pp. 47-52
No summary available.
 
Mapping of languages by two-tape devices
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Seymour Ginsburg, Edwin H. Spanier
Issue Date:November 1964
pp. 57-67
No summary available.
 
Characterization of context-free grammatical families
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Armin Cremers, Seymour Ginsburg
Issue Date:October 1974
pp. 199-204
Two characterization theorems for the class of context-free grammatical families are given. The characterizations are expressed in terms of the family of regular sets, the family of linear sets, and the following language-family operators: union, concatena...
 
Abstract families of languages
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Seymour Ginsburg, Sheila Greibach
Issue Date:October 1967
pp. 128-139
The notion of an abstract family of languages (AFL) as a family of sets of words satisfying certain properties common to many types of formal languages is introduced. Operations preserving AFL are then considered. The concept of an abstract family of accep...
 
Deterministic context free languages
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Seymour Ginsburg, Sheila Greibach
Issue Date:October 1965
pp. 203-220
A number of results about deterministic languages (languages accepted by pushdown automata with no choice of moves) are established. In particular, (1) each deterministic language is unambiguous. (2) the complement of each deterministic language is a deter...
 
Pattern matching by Rs-operations: towards a unified approach to querying sequenced data
Found in: Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (PODS '92)
By Seymour Ginsburg, Xiaoyang Wang
Issue Date:June 1992
pp. 293-300
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...
     
Computation-tuple sequences and object histories
Found in: ACM Transactions on Database Systems (TODS)
By Katsumi Tanaka, Seymour Ginsburg
Issue Date:June 1986
pp. 186-212
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 computati...
     
Sort sets in the relational model
Found in: Journal of the ACM (JACM)
By Richard Hull, Seymour Ginsburg
Issue Date:May 1986
pp. 465-488
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...
     
Tuple sequences and lexicographic indexes
Found in: Journal of the ACM (JACM)
By Serge Abiteboul, Seymour Ginsburg
Issue Date:May 1986
pp. 409-422
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 ...
     
Sort sets in the relational model
Found in: Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems (PODS '83)
By Richard Hull, Seymour Ginsburg
Issue Date:March 1983
pp. 332-339
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 ...
     
Properties of functional-dependency families
Found in: Journal of the ACM (JACM)
By Sami Mohammed Zaiddan, Seymour Ginsburg
Issue Date:July 1982
pp. 678-698
It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar nature of board games. In particular, it is pro...
     
Size complexity in context-free grammars forms
Found in: Journal of the ACM (JACM)
By Nancy Lynch, Seymour Ginsburg
Issue Date:October 1976
pp. 582-598
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 ever...
     
Comparative complexity of grammar forms
Found in: Proceedings of seventh annual ACM symposium on Theory of computing (STOC '75)
By Nancy Lynch, Seymour Ginsburg
Issue Date:May 1975
pp. 153-158
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 efficie...
     
Grammar Schemata
Found in: Journal of the ACM (JACM)
By Armin Gabrielian, Seymour Ginsburg
Issue Date:April 1974
pp. 213-226
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, ...
     
Uniformly erasable AFL
Found in: Proceedings of the fourth annual ACM symposium on Theory of computing (STOC '72)
By Jonathan Goldstine, Seymour Ginsburg, Sheila Carlyle-Greibach
Issue Date:May 1972
pp. 207-213
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 con...
     
Multitape AFA
Found in: Journal of the ACM (JACM)
By Seymour Ginsburg, Sheila Greibach
Issue Date:April 1972
pp. 193-221
Many problems, some of them quite meaningful, have been proved to be recursively unsolvable for programs in general. The paper is directed toward a class of programs where many decision problems are solvable. The equivalence problem has been proved to be u...
     
Intersection-closed full AFL and the recursively enumerable languages
Found in: Proceedings of the third annual ACM symposium on Theory of computing (STOC '71)
By Jonathan Goldstine, Seymour Ginsburg
Issue Date:May 1971
pp. 121-131
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 &euil; {ani/i @@...
     
One-way stack automata
Found in: Journal of the ACM (JACM)
By Michael A. Harrison, Seymour Ginsburg, Sheila A. Greibach
Issue Date:April 1967
pp. 389-418
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...
     
Ambiguity in context free languages
Found in: Journal of the ACM (JACM)
By Joseph Ullian, Seymour Ginsburg
Issue Date:January 1966
pp. 62-89
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 p...
     
Theory of abstract machines
Found in: Communications of the ACM
By Seymour Ginsburg
Issue Date:April 1961
pp. 195
The objective is to investigate significant developments in advanced computers and to explore the relationship between programming and new concepts of computer organization. Two specific studies are in progress: Data Sequencing and Vertical Data Processing...
     
Some remarks on abstract machines
Found in: Preprints of papers presented at the 13th national meeting of the Association for Computing Machinery (ACM '58)
By Seymour Ginsburg
Issue Date:June 1958
pp. 1-3
One of the research units of the current Georgetown University project in Machine Translation has developed a general analysis technique for solving the MT problem, based on the concept of structural transfer from the source to the target language. At the ...
     
 1