Each complexity-two word represents every sufficiently long spike.

DOI10.1007/PL00000341MaRDI QIDQ1771874zbMATH OpenOpenAlexFDO

Authors Nereu E. Burin, J. R. Isbell, Donald Silberger

Publication date 19 April 2005

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00000341

zbMATH Keywords

semigroups of partial functionsuniversal wordsword problem

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Semigroups of transformations, relations, partitions, etc. (20M20)

Review text

Denote by \(k=\{0,1,\dots,k-1\}\) and by \(\text{Prt}(k)\) the composition monoid of all partial functions \(f\subseteq k\times k\). Let \(r_k\) denote the partial function \(\{\langle i,i+1\rangle;\;i=0,\dots,k-2\}\). For \(m,n\) positive integers the authors study the set \(S(m,n)\) of all integers \(k\geq 2\) such that there exists no \(\langle x,y\rangle\in\text{Prt}(k)\times\text{Prt}(k)\) which satisfies \(r_k=x^m\cdot y^n\). It is proved that: (i) Whenever \(m\cdot n\) is odd then \(S(m,n)=\emptyset\). (ii) \(S(m,n)\) is finite and \(S(m,n)=S(n,m)\).

Recommendations

• Compositions de fonctions de commutation partielle
• The reverse spelling of an FPrt-universal word in two letters
• Partial unary operations with long pre-periods
• scientific article; zbMATH DE number 2155203
• scientific article; zbMATH DE number 1444029

Cited in

(3)

• The reverse spelling of an FPrt-universal word in two letters
• scientific article; zbMATH DE number 1444029 (Why is no real title available?)
• Universal terms of complexity three

This page was built for publication: Each complexity-two word represents every sufficiently long spike.

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