License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.51
URN: urn:nbn:de:0030-drops-177030
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17703/
Go to the corresponding LIPIcs Volume Portal

Paperman, Charles ; Salvati, Sylvain ; Soyez-Martin, Claire

An Algebraic Approach to Vectorial Programs

pdf-format:
LIPIcs-STACS-2023-51.pdf (1.0 MB)

Abstract

Vectorial programming, the combination of SIMD instructions with usual processor instructions, is known to speed-up many standard algorithms. Simple regular languages have benefited from this technology. This paper is a first step towards pushing these benefits further. We take advantage of the inner algebraic structure of regular languages and produce high level representations of efficient vectorial programs that recognize certain classes of regular languages.
As a technical ingredient, we establish equivalences between classes of vectorial circuits and logical formalisms, namely unary temporal logic and first order logic. The main result is the construction of compilation procedures that turns syntactic semigroups into vectorial circuits. The circuits we obtain are small in that they improve known upper-bounds on representations of automata within the logical formalisms. The gain is mostly due to a careful sharing of sub-formulas based on algebraic tools.

BibTeX - Entry

@InProceedings{paperman_et_al:LIPIcs.STACS.2023.51,
  author =	{Paperman, Charles and Salvati, Sylvain and Soyez-Martin, Claire},
  title =	{{An Algebraic Approach to Vectorial Programs}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{51:1--51:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17703},
  URN =		{urn:nbn:de:0030-drops-177030},
  doi =		{10.4230/LIPIcs.STACS.2023.51},
  annote =	{Keywords: Automata theory, Semigroups, Vectorisation}
}

Keywords: Automata theory, Semigroups, Vectorisation
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI