The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A checking automaton is equivalent to a one-way nonerasing stack automaton which, once it enters its stack, never again writes on its stack. The checking automaton languages (cal) form a full AFL closed under substitution. If L ⊆ a* is an infinite cal, then L contains an infinite regular set. Consequently, there are one-way nonerasing stack languages (such as (an2|n≥1|)) which are not cal. Let L be...
This paper presents systematic synthesis procedures for Lupanov decoding networks. Decoding networks find applications in computer memories for the selection of a particular item of data addressed by a binary code, in counter circuits, in character-by-character code conversion circuits, in the synthesis of switching functions and also in the theoretical derivations of complexity bounds for arbitrary...
Table languages are extensions of finite state languages and context free languages. Table languages have access to a table on each generation step. Table entries are an ordered pair: (attribute,identifier). The collection of attributes comprise a finite set while the collection of identifiers comprise an infinite regular set. An arbitrary table language generator is in "normal form" when...
A generalization of automata theory is constructed using multivalued functions of several arguments and with several results rather than the single valued functions of a single argument which appear in conventional automata theory. Algebraic rules are developed for composing such functions which enable one to specify an element of a semigroup which represents a composite function and a convenient...
In the first part of this paper, an algorithm is derived for testing a given two state machine for the property of being universal. Various characterizations of universality are also obtained, and are stated in the form of necessary and sufficient conditions. The second part of this paper is concerned with the economical realization of sequential machines as networks of identical modules. Bounds are...
This paper concerns with the problem of comparing structures of automata which are in general incomplete and non-deterministic. It is shown here that in many cases where behavioral equivalence between automata have been established in the literature, those automata are also structurally equivalent. A necessary and sufficient condition is also given for a class of automata to be structurally equivalent.
This paper is concerned with infinite state probabilistic transition tables, representing the dynamical behavior of a probabilistic automaton and nonhomogeneous infinite-state Markov chains. Many known theorems are generalized from the finite state case to the infinite state case. A possible application to the problem of computing, approximately, products of infinite state stochastic matrices is outlined.
In this paper, we extend the partition theory developed by Hartmanis and learns for synchronous sequential circuits to asynchronous sequential circuits. method which utilizes the concept of partition pairs to obtain single transition time asynchronous state assignments with reduced dependence is presented. procedures are also presented for obtaining parallel and serial decompositions of synchronous...
This paper describes an algorithm for minimizing the storage required of a Read Only Memory that is going to be used as the control element for a digital machine. The technique is based upon the fact that not all sub-commands are required in all words so that bits of the memory may be time shared between subcommands. The algorithm provides a means for determining what sub-commands should share a common...
The problem is treated of finding for a set of identical processing elements an interconnection structure that achieves a certain richness of interelement communication with only a limited number of actual inter-element connections. In graphical terms, this problem is one of finding a universal n-node graph of minimal degree D(n,d) in which every n-node graph of maximum degree d is branchembeddable...
Not all switching functions are realizable by a single cascade of 2- input, 1-output switching elements, even if repeated inputs are allowed. However, arrays of such cascades feeding a single collector cascade of AND or OR cells can be used to synthesize any function. This paper is concerned with optimal array realizations of this form. A procedure is given which allows one to generate rather efficiently...
Synthesis techniques are presented for realizing any given synchronous flow table in an array of identical modules interconnected in a regular pattern. Several types of structures and their corresponding modules are considered, and a relationship between these structures and earlier work on combinational circuits is shown.
A program schema consists of operation symbols, predicate symbols and some constant symbols. In this paper we investigate some formal properties of a class of non-deterministic program schemata. In Section I a class of regular program schemata is introduced as a counterpart of Kleene's regular expressions, and we show that any graph schema can be represented by a regular program schema and that two...
An infinite sequence over a finite alphabet is regular if the indices of those positions at which each given symbol occurs in the sequence constitute a set of numbers which in suitable base is recognizable by a finite automaton. A sequence obtained by deleting from a regular sequence all occurrences of certain symbols is semi-regular. Semi-regular sequences are alternatively characterizable as those...
Cellular spaces computationally equivalent to any given Turing machine are exhibited which are simple in the sense that each cell has only a small number of states and a small neighborhood. Neighborhood reduction theorems are derived in this interest, and several simple computationuniversal cellular spaces are presented. Conditions for computation-universality of a cellular space are investigated,...
The need for a measure different from the number of states in analyzing stochastic sequential machines is pointed out. Using the decomposition previously demonstrated in association with actual physical realization of stochastic sequential machines4, a particular measure of complexity C(M) for a given machine M is introduced. The computational aspect of C(M) is discussed and an example exhibiting...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.