License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CALCO.2019.2
URN: urn:nbn:de:0030-drops-114309
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11430/
Go to the corresponding LIPIcs Volume Portal

Milius, Stefan

From Equational Specifications of Algebras with Structure to Varieties of Data Languages (Invited Paper)

pdf-format:
LIPIcs-CALCO-2019-2.pdf (0.3 MB)

Abstract

This extended abstract first presents a new category theoretic approach to equationally axiomatizable classes of algebras. This approach is well-suited for the treatment of algebras equipped with additional computationally relevant structure, such as ordered algebras, continuous algebras, quantitative algebras, nominal algebras, or profinite algebras. We present a generic HSP theorem and a sound and complete equational logic, which encompass numerous flavors of equational axiomizations studied in the literature. In addition, we use the generic HSP theorem as a key ingredient to obtain Eilenberg-type correspondences yielding algebraic characterizations of properties of regular machine behaviours. When instantiated for orbit-finite nominal monoids, the generic HSP theorem yields a crucial step for the proof of the first Eilenberg-type variety theorem for data languages.

BibTeX - Entry

@InProceedings{milius:LIPIcs:2019:11430,
  author =	{Stefan Milius},
  title =	{{From Equational Specifications of Algebras with Structure to Varieties of Data Languages (Invited Paper)}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{2:1--2:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Markus Roggenbach and Ana Sokolova},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11430},
  URN =		{urn:nbn:de:0030-drops-114309},
  doi =		{10.4230/LIPIcs.CALCO.2019.2},
  annote =	{Keywords: Birkhoff theorem, Equational logic, Eilenberg theorem, Data languages}
}

Keywords: Birkhoff theorem, Equational logic, Eilenberg theorem, Data languages
Collection: 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)
Issue Date: 2019
Date of publication: 25.11.2019

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