Decidability of the Orbit Problem for logarithmic-dimensional target subspaces and Skolem-hardness for linear-dimensional targets.
Transducers of polynomial growth (invited talk)
4 Pith papers cite this work, alongside 10 external citations. Polarity classification is still indexing.
4
Pith papers citing it
10
external citations · external index
representative citing papers
A theorem establishes that MSO queries on strings with O(n0 * n1) results can be reparameterized to identify each result from one 0-position, one 1-position and finite data, with the result extending to FO logic.
Algorithms for deciding existence and computing representations of p-adic zeros in linear recurrence sequences, unconditionally correct with termination guaranteed subject to the p-adic Schanuel Conjecture, applied to decidability of the Simultaneous Skolem Problem.
Integer hybrid path-sums plus a sound Hoare logic enable semi-automated functional verification and expected-cost analysis of hybrid quantum programs with unbounded while loops.
citing papers explorer
-
On the Subspace Orbit Problem and the Simultaneous Skolem Problem
Decidability of the Orbit Problem for logarithmic-dimensional target subspaces and Skolem-hardness for linear-dimensional targets.
-
A finer reparameterisation theorem for MSO and FO queries on strings
A theorem establishes that MSO queries on strings with O(n0 * n1) results can be reparameterized to identify each result from one 0-position, one 1-position and finite data, with the result extending to FO logic.
-
On the $p$-adic Skolem Problem
Algorithms for deciding existence and computing representations of p-adic zeros in linear recurrence sequences, unconditionally correct with termination guaranteed subject to the p-adic Schanuel Conjecture, applied to decidability of the Simultaneous Skolem Problem.
-
An Effective Quantum Hoare Logic for Hybrid Quantum Programs with Unbounded Loops
Integer hybrid path-sums plus a sound Hoare logic enable semi-automated functional verification and expected-cost analysis of hybrid quantum programs with unbounded while loops.