Search Results

Documents authored by Roupin, June


Document
The Alternating Normal Form of Braids and Its Minimal Automaton

Authors: Vincent Jugé and June Roupin

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)


Abstract
The alternating normal form of braids is a well-known normal form on standard braid monoids. This normal form is regular: the language it identifies with is regular. We give a characterisation of the minimal automaton of this language and compute its size, both in terms of number of states and of transitions, depending on the number of generators of the monoid.

Cite as

Vincent Jugé and June Roupin. The Alternating Normal Form of Braids and Its Minimal Automaton. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{juge_et_al:LIPIcs.AofA.2024.23,
  author =	{Jug\'{e}, Vincent and Roupin, June},
  title =	{{The Alternating Normal Form of Braids and Its Minimal Automaton}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.23},
  URN =		{urn:nbn:de:0030-drops-204587},
  doi =		{10.4230/LIPIcs.AofA.2024.23},
  annote =	{Keywords: Automata, braids, enumeration, normal forms}
}