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.
A set of equivalences is established among cellular automata, iterative acceptors, and linear-bounded automata. However, cellular automata are shown to be inherently faster than iterative acceptors. Many positive results are presented to indicate that the context-free languages can, perhaps, be accepted in time n and space n by cellular automata.
The problem of designing asynchronous circuits where the changes in binary input signals occur independently of one another is discussed. If several input changes occur within some interval δ1, the circuit behaves as though the changes were simultaneous. If consecutive changes are spaced by intervals exceeding some longer interval δ2 then the circuit reacts as though a sequence of single changes had...
It is an open problem, suggested by Papert and McNaughton, to find a decision procedure for determining whether a regular event is locally testable. In this paper we provide a partial solution, giving two effectively decidable conditions, one necessary and one sufficient, for local testability. Our proofs are for the most part algebraic, using machine decompositions and semigroup theory.
A new flow table for describing normal-fundamental-mode (NFM) asynchronous machines, the ADSE table, is introduced. Although the structure of this table has several ramifications in the area of circuit realization, this paper emphasizes its utility in generating checking experiments for NFM asynchronous machines. Using the ADSE table, a procedure is presented that allows existing (or future) methods...
Syntactic clues are aids to parsing. The amount of nondeterminism in parsers for pairs of homomorphically related semithue language systems is compared. If the parsers are without lookahead, the domain language system parser has no more nondeterminism than the codomain language system parser. The domain language system has at least as many clues. If the parsers have lookahead and the homomorphism...
Optimality, to within a multiplicative constant, is shown for some algorithms dealing with vectors and finite sets. Among the problems discussed are: Is vector x equal to vector y ? Given two finite sets A and B, is A = B ? Is A ⊆ B ? Is A ∩ B = φ ? What is |A ∩ B| ? What is |A - B| ? Is A - B = φ ?
The "deadlock" problem is a logical problem which may occur in a system in which resources are shared among users. Deadlock is a situation in which two or more jobs cannot be completed because of conflicting resource requirements. In this paper we assume that advance information about future resource requirements of jobs is available. In particular, we assume that jobs are represented as...
The aim of this paper is not the establishment of new results, but the understanding, from a machine theoretic point of view, of results originally arrived at by algebraic means. A new criterion for series parallel irreducibility is given which makes no reference to underlying semigroups but involves only series parallel operations. Also, the irreducibility of prime counter machines is established...
Two classes of restricted top down parsing algorithms using backtrack are considered. We show that the smaller class recognizes all deterministic context free languages, and that both classes can be simulated in linear time on a random access machine. Certain generalizations of these parsing algorithms are shown equivalent to the larger class. Finally, some decision and closure properties of the classes...
Left corner parsing refers to a class of parsing procedures in which the productions are recognized in a particular order which is different than both bottom up and top down. Each production is recognized after its left descendant but before its other descendants. Procedures in this class have occurred frequently in the compiler literature. In this paper a class of grammars, called LC (k) grammars,...
The simultaneous use of delayed and undelayed versions of the internal variables permits the realization of normal fundamental mode circuits with less restricted state assignments than the usual single transition time state assignments. This paper is concerned with problems associated with these state assignments.
La représentation matricielle minimale attachée à une série rationnelle en variables non commutatives permet de généraliser à ces séries des résultats connus en théorie des langages. Les méthodes employées permettent aussi d'étudier les parties rationnelles de certains monoïdes comme le groupe libre.
We consider a class of straight line programs admitting structured variables. It is easy to associate with each program a set of expressions which reflects the natural meaning of a structured variable such as an array. However, the question of whether two such expressions are equivalent depends on what is assumed about the possible initial values of the variables and what algebraic laws are assumed...
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.