A preliminary example of program development demonstrates that the control-independent implementation of data types can lead to very inefficient code. The concept of a data space, which emphasizes the interaction between data and control structures, is introduced as a formal model of virtual machines. The model consists of three components: a state space X, an information structure F, and a control component p. Formally, X is a set of objects, F a set of functions with common domain X mapping the states to the value sets of certain data types, and p a partial function X → X. Two important points of investigation are the characterization of state space structure and the mechanism of implementation. Good state description is characterized by "completeness" and "orthogonality." Either property plays a prominent role for the concept of implementation which, in turn, is formally defined as a mapping from a "virtual" space to a "real" space, via some "macro" space. These notions are illugtrated by means of several examples from the area of programming languages.

A phrase structure grammar is called context-limited if there exists a partial ordering on its alphabet such that any letter on the left of any production is less than some letter on the right of the same production. It is proved that context-limited grammars are equivalent to context-free grammars, the equivalence including ambiguity. The notion of ambiguity in phrase structure grammars is discussed, and a new formal model for ambiguity, based on directed plane graphs with labeled edges, is outlined and compared with other models.

Call a (context-free) language unambiguous if it is not inherently ambiguous. In the absence of evidence to the contrary, the suspicion has arisen that the unambiguous languages might be precisely those languages with context-free complements. The two theorems presented in this paper lay the suspicion to rest by providing (1) an inherently ambiguous language with context-free complement and (2) an unambiguous language without context-free complement. This establishes the independence of inherent ambiguity from complementedness among the context-free languages.

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 AccessA Simple Sorting Algorithm Author: Thomas N. Hibbard System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 10Issue 2April 1963 pp 142–150https://doi.org/10.1145/321160.321164Published:01 April 1963Publication History 7citation726DownloadsMetricsTotal Citations7Total Downloads726Last 12 Months48Last 6 weeks21 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 Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting Author: Thomas N. Hibbard System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 9Issue 1Jan. 1962 pp 13–28https://doi.org/10.1145/321105.321108Online:01 January 1962Publication History 101citation961DownloadsMetricsTotal Citations101Total Downloads961Last 12 Months48Last 6 weeks6 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 Least Upper Bounds on Minimal Terminal State Experiments for Two Classes of Sequential Machines Author: Thomas N. Hibbard System Development Corporation, Santa Monica, California System Development Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 8Issue 4Oct. 1961 pp 601–612https://doi.org/10.1145/321088.321098Published:01 October 1961Publication History 36citation327DownloadsMetricsTotal Citations36Total Downloads327Last 12 Months16Last 6 weeks4 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