Groups whose word problem is a Petri net language

Gabriela Rino Nesin, Richard M. Thomas

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBN

Abstract

There has been considerable interest in exploring the connections between the word problem of a finitely generated group as a formal language and the algebraic structure of the group. However, there are few complete characterizations that tell us precisely which groups have their word problem in a specified class of languages. We investigate which finitely generated groups have their word problem equal to a language accepted by a Petri net and give a complete classification, showing that a group has such a word problem if and only if it is virtually abelian.
Original languageEnglish
Title of host publicationInternational Workshop on Descriptional Complexity of Formal Systems
Place of PublicationCham
PublisherSpringer
Pages243-255
Number of pages13
Volume9118
DOIs
Publication statusPublished - 16 Jun 2015
EventInternational Workshop on Descriptional Complexity of Formal Systems - University of Waterloo, Ontario, Canada. DCFS 2015
Duration: 16 Jun 2015 → …

Publication series

NameLecture Notes in Computer Science

Workshop

WorkshopInternational Workshop on Descriptional Complexity of Formal Systems
Period16/06/15 → …

Bibliographical note

The final authenticated version is available online at https://doi.org/10.1007/978-3-319-19225-3_21

Fingerprint Dive into the research topics of 'Groups whose word problem is a Petri net language'. Together they form a unique fingerprint.

Cite this