
An Optimal Construction for the BarthelmannSchwentick Normal Form on Classes of Structures of Bounded Degree
Building on the locality conditions for firstorder logic by Hanf and Ga...
read it

Equation satisfiability in solvable groups
The study of the complexity of the equation satisfiability problem in fi...
read it

Thinness of product graphs
The thinness of a graph is a width parameter that generalizes some prope...
read it

AMSNP: a tame fragment of existential secondorder logic
Amalgamation monotone SNP (AMSNP) is a fragment of existential secondor...
read it

Identifiability of Graphs with Small Color Classes by the WeisfeilerLeman Algorithm
As it is well known, the isomorphism problem for vertexcolored graphs w...
read it

Towards an arboretum of monadically stable classes of graphs
Logical transductions provide a very useful tool to encode classes of st...
read it

Going from the huge to the small: Efficient succinct representation of proofs in Minimal implicational logic
A previous article shows that any linear height bounded normal proof of ...
read it
Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time
In the quest for a logic capturing PTime the next natural classes of structures to consider are those with bounded color class size. We present a canonization procedure for graphs with dihedral color classes of bounded size in the logic of Choiceless Polynomial Time (CPT), which then captures PTime on this class of structures. This is the first result of this form for nonabelian color classes. The first step proposes a normal form which comprises a "rigid assemblage". This roughly means that the local automorphism groups form 2injective 3factor subdirect products. Structures with color classes of bounded size can be reduced canonization preservingly to normal form in CPT. In the second step, we show that for graphs in normal form with dihedral color classes of bounded size, the canonization problem can be solved in CPT. We also show the same statement for general ternary structures in normal form if the dihedral groups are defined over odd domains.
READ FULL TEXT
Comments
There are no comments yet.