Outrunning Big KATs: Efficient Decision Procedures for Variants of GKAT

Cheng Zhang, Qiancheng Fu, Hang Ji, Ines Santacruz Del Valle, Alexandra Silva, Marco Gaboardi · 2026

Read Outrunning Big KATs: Efficient Decision Procedures for Variants of GKAT by Cheng Zhang, Qiancheng Fu, Hang Ji, Ines Santacruz Del Valle, Alexandra Silva, Marco Gaboardi (2026) 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-2601-09986.txt.

Description

Cheng Zhang and co authors speed up checks for a class of programs. The programs are GKAT automata. They mix tests, loops, and acts. A check asks if two such programs act the same on all traces.

Checks of this kind can be slow. The team gives fast checks that work on the fly. They use SAT tools to search for a gap. To show use, they built a tool for code flow checks. It tests if a change to code flow keeps the acts the same. Fast checks of this sort help keep code changes safe.

Catalog record

CREATORCheng Zhang, Qiancheng Fu, Hang Ji, Ines Santacruz Del Valle, Alexandra Silva, Marco Gaboardi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE196 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-09986

Browse the full library · About the Tower of Babel