A General Completeness Theorem for Skip-free Star Algebras

Tobias Kappé, Todd Schmid · 2025

Read A General Completeness Theorem for Skip-free Star Algebras by Tobias Kappé, Todd Schmid (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-15325.txt.

Description

Tobias Kappé and Todd Schmid present a 2025 paper in computer science logic on process algebras, formal systems that model programs that branch and loop. A key question is when a set of rules fully captures when two processes act the same. The authors study skip-free star algebras, a family where the branching rules can be set by a chosen equation theory. They prove a broad completeness result for that family.

Their proof lifts an earlier argument to a general form. New cases fall out, among them systems with chance-based guarded branching. Older completeness results also drop out as special cases. A general theorem of this kind saves each subfield from redoing the same hard proof. The work serves logicians who build process tools.

Catalog record

CREATORTobias Kappé, Todd Schmid
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE134 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-15325

Browse the full library · About the Tower of Babel