Deciding conjugacy in sylvester monoids and other homogeneous monoids

Alan J. Cain; Antonio Malheiro

doi:10.1142/S0218196715500241

Deciding conjugacy in sylvester monoids and other homogeneous monoids

Alan J. Cain, Antonio Malheiro

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

66 Downloads (Pure)

Abstract

We give a combinatorial characterization of conjugacy in the sylvester monoid, showing that conjugacy is decidable for this monoid. We then prove that conjugacy is undecidable in general for homogeneous monoids and even for multihomogeneous monoids.

Original language	English
Pages (from-to)	899-915
Number of pages	17
Journal	International Journal Of Algebra And Computation
Volume	25
Issue number	5
DOIs	https://doi.org/10.1142/S0218196715500241
Publication status	Published - 18 Aug 2015

Keywords

Conjugacy
decidability
homogeneous monoid
sylvester monoid (the monoid of binary search trees)

Access to Document

10.1142/S0218196715500241Licence: Unspecified

1404.2618Accepted author manuscript, 176 KB

Cite this

@article{fb295ae1a78342638f6b36de9377a0f6,

title = "Deciding conjugacy in sylvester monoids and other homogeneous monoids",

abstract = "We give a combinatorial characterization of conjugacy in the sylvester monoid, showing that conjugacy is decidable for this monoid. We then prove that conjugacy is undecidable in general for homogeneous monoids and even for multihomogeneous monoids.",

keywords = "Conjugacy, decidability, homogeneous monoid, sylvester monoid (the monoid of binary search trees)",

author = "Cain, {Alan J.} and Antonio Malheiro",

note = "info:eu-repo/grantAgreement/FCT/5876/135994/PT# info:eu-repo/grantAgreement/FCT/5876/147204/PT# Project PEST-C/MAT/UI0144/2011. fellowship (IF/01622/2013/CP1161/CT0001). ",

year = "2015",

month = aug,

day = "18",

doi = "10.1142/S0218196715500241",

language = "English",

volume = "25",

pages = "899--915",

journal = "International Journal Of Algebra And Computation",

issn = "0218-1967",

publisher = "World Scientific",

number = "5",

}

TY - JOUR

T1 - Deciding conjugacy in sylvester monoids and other homogeneous monoids

AU - Cain, Alan J.

AU - Malheiro, Antonio

N1 - info:eu-repo/grantAgreement/FCT/5876/135994/PT# info:eu-repo/grantAgreement/FCT/5876/147204/PT# Project PEST-C/MAT/UI0144/2011. fellowship (IF/01622/2013/CP1161/CT0001).

PY - 2015/8/18

Y1 - 2015/8/18

N2 - We give a combinatorial characterization of conjugacy in the sylvester monoid, showing that conjugacy is decidable for this monoid. We then prove that conjugacy is undecidable in general for homogeneous monoids and even for multihomogeneous monoids.

AB - We give a combinatorial characterization of conjugacy in the sylvester monoid, showing that conjugacy is decidable for this monoid. We then prove that conjugacy is undecidable in general for homogeneous monoids and even for multihomogeneous monoids.

KW - Conjugacy

KW - decidability

KW - homogeneous monoid

KW - sylvester monoid (the monoid of binary search trees)

UR - http://www.scopus.com/inward/record.url?scp=84939567901&partnerID=8YFLogxK

U2 - 10.1142/S0218196715500241

DO - 10.1142/S0218196715500241

M3 - Article

AN - SCOPUS:84939567901

SN - 0218-1967

VL - 25

SP - 899

EP - 915

JO - International Journal Of Algebra And Computation

JF - International Journal Of Algebra And Computation

IS - 5

ER -

Deciding conjugacy in sylvester monoids and other homogeneous monoids

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this