Kenneth Gill

activity

20162024

collaborators

4 papers

cs.FL2024

Probabilistic automatic complexity of finite strings

Kenneth Gill

We introduce a new complexity measure for finite strings using probabilistic finite-state automata (PFAs), in the same spirit as existing notions employing DFAs and NFAs, and explo…

math.LO2023

Indivisibility and uniform computational strength

Kenneth Gill

A countable structure is indivisible if for every coloring with finite range there is a monochromatic isomorphic subcopy of the structure. Each indivisible structure naturally corr…

math.LO2023

A note on the indivisibility of the Henson graphs

Kenneth Gill

We show that in contrast to the Rado graph, the Henson graphs are not computably indivisible.

math.CO2016

Signed tilings by ribbon L n-ominoes, n even, via Groebner bases

Kenneth Gill, Viorel Nitica

Let $T_{n}$ be the set of ribbon $L$ -shaped $n$ -ominoes for some $n \geq 4$ even, and let $T_{n}^{+}$ be $T_{n}$ with an extra $2 \times 2$ square. We investigat…