RUS  ENG
Full version
JOURNALS // Vestnik TVGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics] // Archive

Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2008, Issue 10, Pages 25–36 (Mi vtpmk381)

Mathematical Foundations of Computer Science

On the inexpressibility a linear order by means of non-deterministic programs in groupoids of a special type

I. V. Popov

Tver State University, Tver

Abstract: In this paper we consider a special class of groupoids, which was presented in the article by M.A.Taitslin "Пример полиномиального запроса не распознаваемого в недетерминированной логарифмической памяти". In this paper we study a question of unexpressibility of linear order on the elements of such groupoid using non-determined programs. It is shown, that the question of linear order unexpressibility can be reduced to the question of unsolvability of some equations system in four-element quasi-group.

Keywords: non-determined programs, linear order, linear programs, quasi-groups.

UDC: 510.676, 519.7

Received: 07.04.2008
Revised: 24.09.2008



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024