Rewriting systems, plain groups, and geodetic graphs

Murray Elder; Adam Piggott

doi:10.1016/j.tcs.2021.12.022

Rewriting systems, plain groups, and geodetic graphs

Murray Elder^*, Adam Piggott

^*Corresponding author for this work

Mathematical Sciences Institute

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

5 Citations (Scopus)

Abstract

We take a new step towards an algebraic characterisation of groups presented by length-reducing rewriting systems. We prove that a group is presented by finite convergent length-reducing rewriting systems where each rule has left-hand side of length three if and only if the group is plain.

Our proof rests on proving a new result about embedded circuits in geodetic graphs, whose proof may also be of independent interest to graph theorists.

Original language	English
Pages (from-to)	134-144
Number of pages	11
Journal	Theoretical Computer Science
Volume	903
DOIs	https://doi.org/10.1016/j.tcs.2021.12.022
Publication status	Published - 8 Feb 2022

Access to Document

10.1016/j.tcs.2021.12.022

Cite this

@article{0a3d5bf7565e47bd8f67f00f2c38635d,

title = "Rewriting systems, plain groups, and geodetic graphs",

abstract = "We take a new step towards an algebraic characterisation of groups presented by length-reducing rewriting systems. We prove that a group is presented by finite convergent length-reducing rewriting systems where each rule has left-hand side of length three if and only if the group is plain.Our proof rests on proving a new result about embedded circuits in geodetic graphs, whose proof may also be of independent interest to graph theorists.",

keywords = "Geodetic graph, Length-reducing rewriting system, Plain group",

author = "Murray Elder and Adam Piggott",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2022",

month = feb,

day = "8",

doi = "10.1016/j.tcs.2021.12.022",

language = "English",

volume = "903",

pages = "134--144",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Rewriting systems, plain groups, and geodetic graphs

AU - Elder, Murray

AU - Piggott, Adam

PY - 2022/2/8

Y1 - 2022/2/8

N2 - We take a new step towards an algebraic characterisation of groups presented by length-reducing rewriting systems. We prove that a group is presented by finite convergent length-reducing rewriting systems where each rule has left-hand side of length three if and only if the group is plain.Our proof rests on proving a new result about embedded circuits in geodetic graphs, whose proof may also be of independent interest to graph theorists.

AB - We take a new step towards an algebraic characterisation of groups presented by length-reducing rewriting systems. We prove that a group is presented by finite convergent length-reducing rewriting systems where each rule has left-hand side of length three if and only if the group is plain.Our proof rests on proving a new result about embedded circuits in geodetic graphs, whose proof may also be of independent interest to graph theorists.

KW - Geodetic graph

KW - Length-reducing rewriting system

KW - Plain group

UR - https://www.scopus.com/pages/publications/85122254714

U2 - 10.1016/j.tcs.2021.12.022

DO - 10.1016/j.tcs.2021.12.022

M3 - Article

SN - 0304-3975

VL - 903

SP - 134

EP - 144

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Rewriting systems, plain groups, and geodetic graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this