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.
This paper attempts to use formal semantics of a class of parallel processes in order to carry out mechanizable proofs about them. The formalism used is LCF (Logic for Computable Functions, Milner [22]), with slight extensions. The processes we consider communicate by sharing memory, rather than by signals on communication lines. Parallelism is treated as nondeterminism. We state properties such as...
The inclusion problem for the class of monadic recursion schemes is shown to be undecidable, thus answering an open question of Paterson [5]. The proof depends upon a construction similar to one used showing that the question "is L1 ⊆ L2 ?" is undecidable for context-free languages L1, L2.
In 1970, Knuth, Pratt, and Morris [1] showed how to do basic pattern matching in linear time. Related problems, such as those discussed in [4], have previously been solved by efficient but sub-optimal algorithms. In this paper, we introduce an interesting data structure called a bi-tree. A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented...
This paper deals with hazards on outputs of combinational circuits without feedback for multiple input changes. A procedure is given to decompose a Boolean function into a feedback free circuit. The procedure either gives a logic hazard-free circuit or shows that the Boolean function cannot be broken down into a feedback free circuit which is free of logic hazards for multiple input changes.
A notion of one computable function (not) helping the computation of another is defined in terms of the lattices of honest subrecursive classes. It is said that two honest computable functions do not help each other's computation if the intersection (meet) of the subrecursive classes which they generate is the zero subrecursive class; that is, two functions do not help each other's computation if...
We investigate the size of sets of computable functions using category-theoretic methods (in the sense of the Baire Category theorem). Constructive definitions of no-where dense and meagre set are given and applied to several problems. In particular we apply it to subrecursive degree structures and to a comparison of the power of deterministic and nondeterministic time bounded oracle machines.
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.