Word problems in Elliott monoids

DOI10.1016/J.AIM.2018.07.015MaRDI QIDQ1669037zbMATH OpenOpenAlexFDO

Publication date 29 August 2018

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.01947

word problem AF algebra Elliott classification Behncke-Leptin algebras Effros-Shen algebra Farey AF algebra

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Ordered abelian groups, Riesz groups, ordered linear spaces (06F20) (K)-theory and operator algebras (including cyclic theory) (46L80) MV-algebras (06D35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Abstract operator algebras on Hilbert spaces (47L30) Descriptive complexity and finite models (68Q19) Limit algebras, subalgebras of (C^*)-algebras (47L40) Word problems (aspects of algebraic structures) (08A50) Free lattices, projective lattices, word problems (06B25) Word problems, etc. in computability and recursion theory (03D40)

Abstract: Algorithmic issues concerning Elliott local semigroups are seldom considered in the literature, although these combinatorial structures completely classify AF algebras. In general, the addition operation of an Elliott local semigroup is {it partial}, but for every AF algebra

m a t h f r a k B

whose Murray-von Neumann order of projections is a lattice, this operation is uniquely extendible to the addition of an involutive monoid

E (m a t h f r a k B)

. Let

m a t h f r a k M_{1}

be the Farey AF algebra introduced by the present author in 1988 and rediscovered by F. Boca in 2008. The freeness properties of the involutive monoid

E (m a t h f r a k M_{1})

yield a natural word problem for every AF algebra

m a t h f r a k B

with singly generated

E (m a t h f r a k B)

, because

m a t h f r a k B

is automatically a quotient of

m a t h f r a k M_{1}

. Given two formulas

p h i

and

p s i

in the language of involutive monoids, the problem asks to decide whether

p h i

and

p s i

code the same equivalence of projections of

m a t h f r a k B

. This mimics the classical definition of the word problem of a group presented by generators and relations. We show that the word problem of

m a t h f r a k M_{1}

is solvable in polynomial time, and so is the word problem of the Behnke-Leptin algebras

m a t h c a l A_{n, k}

, and of the Effros-Shen algebras

m a t h f r a k F_{h e t a}

, for

h e t a i n [0, 1] s e t m i n u s m a t h b b Q

a real algebraic number, or

h e t a = 1 / e

. We construct a quotient of

m a t h f r a k M_{1}

having a G"odel incomplete word problem, and show that no primitive quotient of

m a t h f r a k M_{1}

is G"odel incomplete.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Word problems in Elliott monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1669037)