Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: unary algebra

Sortuj według:

Ogranicz wyniki do:

On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity

100%

Šíma J. , Žák S.

tom Vol. 152, nr 4

397--409

We formulate a very general tight diagonalization method for the Blum complexity measures satisfying two additional axioms related to our diagonalizer machine. We apply this method to two new, mutually related, distance and buffer complexities of Turing machine computations which are important nontrivial examples of natural Blum complexity measures different from time and space. In particular, these measures capture how many times the worktape head needs to move a certain distance during the computation which corresponds to the number of necessary block uploads into a buffer cache memory. We start this study by proving a tight separation which shows that a very small increase in the distance or buffer complexity bound (roughly from f(n) to f(n + 1)) brings provably more computational power to both deterministic and nondeterministic Turing machines even for unary languages. We also obtain hierarchies of the distance and buffer complexity classes.

Subalgebra lattices of a partial unary algebra

86%

Pióro K.

2012

tom Vol. 45, nr 4

755-777

Necessary and sufficient conditions will be found for quadruples of lattices to be isomorphic to lattices of weak, relative, strong subalgebras and initial segments, respectively, of one partial unary algebra. To this purpose we will start with a characterization of pairs of lattices that are weak and strong subalgebra lattices of one partial unary algebra, respectively. Next, we will describe the initial segment lattice of a partial unary algebra. Applying this result, pairs of lattices of strong subalgebras and initial segments will be characterized. Further, we will characterize pairs of lattices of relative and strong subalgebras and also other pairs of subalgebra lattices of one partial unary algebra.