6 papers
Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
Antonios Kalampakas
The Weisfeiler-Leman (WL) algorithm tests graph isomorphism by assigning colours to -tuples of vertices and iteratively refining the colouring according to neighbourhood configu…
Graphoid Automata, Frobenius PROPs, and Semiring Evaluation
Antonios Kalampakas
Graphoid automata evaluate graphs by composing relations between words of states. We examine the equations that make this evaluation independent of the chosen graph expression, and…
Width-Bounded Equational Derivations for Finite Graph Expressions
Antonios Kalampakas
Completeness of an equational presentation guarantees an equality path but need not control the resources used along it. For finite graph expressions we measure derivational space…
Automatic constraints with few subpowers and graphoid recognition
Antonios Kalampakas
Finite automata can describe relations of unbounded arity that are exponentially larger than their descriptions. We prove that constraint satisfaction for such relations is solvabl…
Recognizability equals CMSO-definability for graphs of rank-width at most two
Antonios Kalampakas
We prove that, on finite graphs of rank-width at most two, VR-recognizability and counting monadic second-order definability coincide. This advances the recognizability-versus-defi…
Split-Free Cable Expressions: Active Neighborhood Profiles and Linear Rank-Width
Antonios Kalampakas
We introduce split-free cable expressions and their sequential restriction. Live cables are vertex blocks that future operations cannot split. The main result identifies sequential…