Cover Image

Completeness Theorems for Kleene algebra with tests and top

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pous, Damien, Wagemaker, Jana
Format:	Preprint
Published:	2023
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Kleene Theorem for Higher-Dimensional Automata
by: Fahrenberg, Uli, et al.
Published: (2022)

Combinatorial manifolds and Kleene's theorem, homotopically
by: Chamoun, Yorgo
Published: (2026)

An Elementary Proof of the FMP for Kleene Algebra
by: Kappé, Tobias
Published: (2022)

A Factorization Theorem for Forest Algebras
by: Almagor, Shaull, et al.
Published: (2026)

Myhill-Nerode Theorem for Higher-Dimensional Automata
by: Fahrenberg, Uli, et al.
Published: (2022)

Completely Reachable Almost Group Automata
by: Torres, David Fernando Casas
Published: (2024)

Büchi-Elgot-Trakhtenbrot Theorem for Higher-Dimensional Automata
by: Amrane, Amazigh, et al.
Published: (2025)

Kamp Theorem for Pomset Languages of Higher Dimensional Automata
by: Clement, Emily, et al.
Published: (2024)

Commutative algebras of series
by: Clemente, Lorenzo
Published: (2026)

Forbidden-Context & Ordered Grammar Systems
by: Fernau, Henning, et al.
Published: (2026)

The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently
by: Lehtinen, Karoliina, et al.
Published: (2025)

A Regular and Complete Notion of Delay for Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2022)

Normal Forms for Elements of ${}^*$-Continuous Kleene Algebras Representing the Context-Free Languages
by: Hopkins, Mark, et al.
Published: (2023)

Minimizing Streaming String Transducers: An algebraic approach
by: Benalioua, Yahia Idriss, et al.
Published: (2026)

Well-Behaved (Co)algebraic Semantics of Regular Expressions in Dafny
by: Zetzsche, Stefan, et al.
Published: (2024)

Completely reachable automata: a quadratic decision algorithm and a quadratic upper bound on the reaching threshold
by: Ferens, Robert, et al.
Published: (2022)

Congruence based proofs of the recognizability theorems for free many-sorted algebras
by: Vidal, Juan Climent, et al.
Published: (2018)

A Completeness Theorem for Probabilistic Regular Expressions
by: Różowski, Wojciech, et al.
Published: (2023)

Time for Quiescence: Modelling quiescent behaviour in testing via time-outs in timed automata
by: Briones, Laura Brandán, et al.
Published: (2025)

Characterization of deterministically recognizable weighted tree languages over commutative semifields by finitely generated and cancellative scalar algebras
by: Fülöp, Zoltán, et al.
Published: (2025)

Benchmarking Testing in Automated Theorem Proving
by: Kim, Jongyoon, et al.
Published: (2026)

A cyclic proof system for Guarded Kleene Algebra with Tests (full version)
by: Rooduijn, Jan, et al.
Published: (2024)

Completeness for categories of generalized automata
by: Boccali, Guido, et al.
Published: (2023)

Characterizing Implementability of Global Protocols with Infinite States and Data
by: Li, Elaine, et al.
Published: (2024)

Robust MITL planning under uncertain navigation times
by: Linard, Alexis, et al.
Published: (2024)

On the Completeness and Ordering of Path-Complete Barrier Functions
by: Anand, Mahathi, et al.
Published: (2025)

Kleene Theorems for Lasso Languages and $ω$-Languages
by: Cruchten, Mike
Published: (2024)

Completing the picture for the Skolem Problem on order-4 linear recurrence sequences
by: Bacik, Piotr
Published: (2024)

Generalised Möbius Categories and Convolution Kleene Algebras
by: Cranch, James, et al.
Published: (2025)

Word-Representable Graphs and Locality of Words
by: Böll, Philipp, et al.
Published: (2025)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
by: Yamakami, Tomoyuki
Published: (2021)

Complete FSM Testing Using Strong Separability
by: Hierons, Robert M., et al.
Published: (2025)

TheoremLlama: Transforming General-Purpose LLMs into Lean4 Experts
by: Wang, Ruida, et al.
Published: (2024)

The Expansion Problem for Infinite Trees
by: Blumensath, Achim
Published: (2023)

Mata, a Fast and Simple Finite Automata Library (Technical Report)
by: Chocholatý, David, et al.
Published: (2023)

Simulation Limitations of Affine Cellular Automata
by: Hudcová, Barbora, et al.
Published: (2023)

On the Expressive Power of Regular Expressions with Backreferences
by: Nogami, Taisei, et al.
Published: (2023)

Safety and Liveness of Quantitative Properties and Automata
by: Boker, Udi, et al.
Published: (2023)

Note on dissecting power of regular languages
by: Rukavicka, Josef
Published: (2023)

Optimal Approximate Minimization of One-Letter Weighted Finite Automata
by: Lacroce, Clara, et al.
Published: (2023)