Serwis Infona wykorzystuje pliki cookies (ciasteczka). Są to wartości tekstowe, zapamiętywane przez przeglądarkę na urządzeniu użytkownika. Nasz serwis ma dostęp do tych wartości oraz wykorzystuje je do zapamiętania danych dotyczących użytkownika, takich jak np. ustawienia (typu widok ekranu, wybór języka interfejsu), zapamiętanie zalogowania. Korzystanie z serwisu Infona oznacza zgodę na zapis informacji i ich wykorzystanie dla celów korzytania z serwisu. Więcej informacji można znaleźć w Polityce prywatności oraz Regulaminie serwisu. Zamknięcie tego okienka potwierdza zapoznanie się z informacją o plikach cookies, akceptację polityki prywatności i regulaminu oraz sposobu wykorzystywania plików cookies w serwisie. Możesz zmienić ustawienia obsługi cookies w swojej przeglądarce.
Previous papers have shown that for any given n-input synchronous sequential machine there exists a circuit realization in which the circuit consists of a finite number of identical copies of one module and in which the modules are interconnected in a uniform manner. This paper shows that additionally the signal fan-in to every module and the signal fan-out from every module and from the input can...
It is shown that a class of languages is defined by a class of two-way deterministic balloon automata if and only if that class is closed under marked union, marked Kleene closure and the inverse mappings performed by GSM's that move two ways on the input. Hence, the context sensitive languages and various time and tape complexity classes are equivalent to classes of 2DBA.
Some new techniques for finding minimal set of tests which detect faults in combinational logic networks are described. A systematic procedure which can be programmed on a digital computer is given. Moreover, a new approach to the design of fault detection experiments for sequential machines which takes into account the actual construction of the sequential network is described.
The automata roots of path sensitizing fault diagnosis are discussed. It is demonstrated that the path sensitizing diagnosis method is equivalent to a Moore type "machine identification" experiment for a machine class which contains good and faulty copies of a transmission path submachine of a complete machine. The maximum length of a complete set of path sensitizing tests for a machine...
Let Φ be any abstract measure of computational complexity, and let L denote the specific measure of memory resource (tape) on one tape Turing machines. Denote by Rt( )Φ the class of all total functions whose Φ-complexity is bounded by the function t( ) almost everywhere. Call such classes Φ-complexity classes. We are interested in relationships among these classes, under proper set inclusion (⊂)....
Some properties of multiprocessing systems, i.e. computing systems in which a set of computational elements share a pool of storage elements are investigated. In particular, the conditions for the output-functionality of these systems are studied, where a computing systems is defined as being output-functional when it produces the same sequence of outputs for the same program, initial state, and input...
Results on two distinct aspects of the theory of probabilistic automata (PA) are presented. Part I is devoted to two generalizations of the theory of loop-free decomposition of stochastic finite-state systems formulated by G. Bacon. The first generalization consists of making a modification in the decomposition scheme of Bacon to allow for the decomposition of a larger class of systems. The second...
This paper is concerned with the recognition of Context-free and deterministic 1-way stack (sa) languages, using n-dimensional Iterative Finitestate Automata (n-D IFA). A problem posed by Cole3 is also answered.
Iterative procedures have many advantages for computation, for instance an approximation to the final answer is provided even if the computation stops abruptly. A model for iterative computation is proposed where a procedure G executed repeatedly "converges" to a function f. A notion of approximation of functions on the integers is used based on limits of densities. Some results on the power...
This paper continues investigations pertaining to recursive bounds on computing resources (such as time or memory) and the amount by which these bounds must be increased if new computations are to occur within the new bound. The paper proves that no recursive operator can increase every recursive bound enough to reach new computations. In other words, given any general recursive operator F[ ], there...
Despite the numerous threshold logic synthesis methods developed in the past decade, the logic designer is still handicapped by the technological independent characterization of these methods. Hence, it has long been the desire for the logic designer to have a simple, efficient threshold-logic synthesis method, analogous to conventional Boolean synthesis using ANDs, ORs, or combinations of ANDs and...
A new type of grammar, called a parallel leveled grammar, is introduced. The families of languages generated by such grammars with contextfree, linear or right-linear subrules are studied. Right-linear parallel finite-leveled languages can be displayed as nested vector expressions, which are extensions of regular expressions. Various hierarchy theorems for these families of languages are obtained...
In this paper, we have introduced a new style of formal grammars called String Adjunct Grammars (AG). The rules in an AG have a considerably different formal character as compared to the 'rewrite rule' in a Phrase Structure Grammar (PSG). Such a study of formal grammars of different styles (i.e., formal character of rules) is of great interest because each style is well suited for characterizing certain...
A superAFL is a family of languages closed under union with unitary sets, intersection with regular sets, and nested iterated substitution and containing at least one nonunitary set. Every superAFL is a full AFL containing all context-free languages. If L is a full principal AFL, then S∞(L, the least superAFL containing L, is full principal. If L is not substitution closed, the substitution closure...
Podaj zakres dat dla filtrowania wyświetlonych wyników. Możesz podać datę początkową, końcową lub obie daty. Daty możesz wpisać ręcznie lub wybrać za pomocą kalendarza.