Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 4

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

Šíma J., Žák S.

Fundamenta Informaticae

2017

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

Pióro K.

Demonstratio Mathematica

2012

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.

Yet another note on congruence uniformity

Goldstern M.

Demonstratio Mathematica

2005

Vol. 38, nr 3

517--521

We describe a countable unary algebra with few operations which is congruence uniform but not congruence regular, and we show that no uncountable algebra with these properties exists.

A note on configurence uniformity for single algebras

Chajda I., Länger H.

Demonstratio Mathematica

2004

Vol. 37, nr 1

9--11

It is proved that though for varieties congruence uniformity implies congruence regularity this is not the case with infinite algebras.