4 papers
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…