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 ISBNResearchpeer-review

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 → …

Fingerprint

Word problem
Petri Nets
Finitely Generated Group
Formal Languages
Algebraic Structure
If and only if
Language

Bibliographical note

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

Cite this

Rino Nesin, G., & Thomas, R. M. (2015). Groups whose word problem is a Petri net language. In International Workshop on Descriptional Complexity of Formal Systems (Vol. 9118, pp. 243-255). (Lecture Notes in Computer Science). Cham: Springer. https://doi.org/10.1007/978-3-319-19225-3_21
Rino Nesin, Gabriela ; Thomas, Richard M. / Groups whose word problem is a Petri net language. International Workshop on Descriptional Complexity of Formal Systems. Vol. 9118 Cham : Springer, 2015. pp. 243-255 (Lecture Notes in Computer Science).
@inproceedings{f897a9cc1a0642efb89e6700cab281c6,
title = "Groups whose word problem is a Petri net language",
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.",
author = "{Rino Nesin}, Gabriela and Thomas, {Richard M.}",
note = "The final authenticated version is available online at https://doi.org/10.1007/978-3-319-19225-3_21",
year = "2015",
month = "6",
day = "16",
doi = "10.1007/978-3-319-19225-3_21",
language = "English",
volume = "9118",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "243--255",
booktitle = "International Workshop on Descriptional Complexity of Formal Systems",

}

Rino Nesin, G & Thomas, RM 2015, Groups whose word problem is a Petri net language. in International Workshop on Descriptional Complexity of Formal Systems. vol. 9118, Lecture Notes in Computer Science, Springer, Cham, pp. 243-255, International Workshop on Descriptional Complexity of Formal Systems, 16/06/15. https://doi.org/10.1007/978-3-319-19225-3_21

Groups whose word problem is a Petri net language. / Rino Nesin, Gabriela; Thomas, Richard M.

International Workshop on Descriptional Complexity of Formal Systems. Vol. 9118 Cham : Springer, 2015. p. 243-255 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBNResearchpeer-review

TY - GEN

T1 - Groups whose word problem is a Petri net language

AU - Rino Nesin, Gabriela

AU - Thomas, Richard M.

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

PY - 2015/6/16

Y1 - 2015/6/16

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-19225-3_21

DO - 10.1007/978-3-319-19225-3_21

M3 - Conference contribution with ISSN or ISBN

VL - 9118

T3 - Lecture Notes in Computer Science

SP - 243

EP - 255

BT - International Workshop on Descriptional Complexity of Formal Systems

PB - Springer

CY - Cham

ER -

Rino Nesin G, Thomas RM. Groups whose word problem is a Petri net language. In International Workshop on Descriptional Complexity of Formal Systems. Vol. 9118. Cham: Springer. 2015. p. 243-255. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-19225-3_21