Source author record

George Kenison

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT Discrete Mathematics Computational Complexity math.DS math.GR Programming Languages

Catalog footprint

Research overview

5works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the Skolem Problem for Reversible Sequences

Given an integer linear recurrence sequence $\langle X_n \rangle_n$ , the Skolem Problem asks to determine whether there is a natural number $n$ such that $X_n = 0$ . Recent work by Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell proved that the Skolem Problem is decidable for a class of reversible sequences of order at most seven. Here we give an alternative proof of their result. Our novel approach employs a powerful result for Galois conjugates that lie on two concentric circles due to Dubickas and Smyth.

preprint2022arXiv

Solving Invariant Generation for Unsolvable Loops

Automatically generating invariants, key to computer-aided analysis of probabilistic and deterministic programs and compiler optimisation, is a challenging open problem. Whilst the problem is in general undecidable, the goal is settled for restricted classes of loops. For the class of solvable loops, introduced by Kapur and Rodríguez-Carbonell in 2004, one can automatically compute invariants from closed-form solutions of recurrence equations that model the loop behaviour. In this paper we establish a technique for invariant synthesis for loops that are not solvable, termed unsolvable loops. Our approach automatically partitions the program variables and identifies the so-called defective variables that characterise unsolvability. We further present a novel technique that automatically synthesises polynomials, in the defective variables, that admit closed-form solutions and thus lead to polynomial loop invariants. Our implementation and experiments demonstrate both the feasibility and applicability of our approach to both deterministic and probabilistic programs.

preprint2020arXiv

On Positivity and Minimality for Second-Order Holonomic Sequences

An infinite sequence $\langle{u_n}\rangle_{n\in\mathbb{N}}$ of real numbers is holonomic (also known as P-recursive or P-finite) if it satisfies a linear recurrence relation with polynomial coefficients. Such a sequence is said to be positive if each $u_n \geq 0$ , and minimal if, given any other linearly independent sequence $\langle{v_n}\rangle_{n \in\mathbb{N}}$ satisfying the same recurrence relation, the ratio $u_n/v_n$ converges to $0$ . In this paper, we focus on holonomic sequences satisfying a second-order recurrence $g_3(n)u_n = g_2(n)u_{n-1} + g_1(n)u_{n-2}$ , where each coefficient $g_3, g_2,g_1 \in \mathbb{Q}[n]$ is a polynomial of degree at most $1$ . We establish two main results. First, we show that deciding positivity for such sequences reduces to deciding minimality. And second, we prove that deciding minimality is equivalent to determining whether certain numerical expressions (known as periods, exponential periods, and period-like integrals) are equal to zero. Periods and related expressions are classical objects of study in algebraic geometry and number theory, and several established conjectures (notably those of Kontsevich and Zagier) imply that they have a decidable equality problem, which in turn would entail decidability of Positivity and Minimality for a large class of second-order holonomic sequences.

preprint2020arXiv

On the Skolem Problem and Prime Powers

The Skolem Problem asks, given a linear recurrence sequence $(u_n)$ , whether there exists $n\in\mathbb{N}$ such that $u_n=0$ . In this paper we consider the following specialisation of the problem: given in addition $c\in\mathbb{N}$ , determine whether there exists $n\in\mathbb{N}$ of the form $n=lp^k$ , with $k,l\leq c$ and $p$ any prime number, such that $u_n=0$ .

preprint2016arXiv

Orbit counting in conjugacy classes for free groups acting on trees

In this paper we study the action of the fundamental group of a finite metric graph on its universal covering tree. We assume the graph is finite, connected and the degree of each vertex is at least three. Further, we assume an irrationality condition on the edge lengths. We obtain an asymptotic for the number of elements in a fixed conjugacy class for which the associated displacement of a given base vertex in the universal covering tree is at most $T$ . Under a mild extra assumption we also obtain a polynomial error term.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.