7 citations · 26 across the 17 of their papers we have counts for
6 papers · 1 filter
Constant time testability of first-order logic with modulo counting on finitary graphs
Isolde Adler, Jenny Stimpson
This paper studies algorithmic meta theorems for property testing with \emph{constant running time} in the bounded degree model. In (Adler, Harwath 2018) it was shown that on graph…
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing
Isolde Adler, Noleen Köhler, Pan Peng
We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that…
Faster Property Testers in a Variation of the Bounded Degree Model
Isolde Adler, Polly Fahey
Property testing algorithms are highly efficient algorithms, that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from…
On Testability of First-Order Properties in Bounded-Degree Graphs
Isolde Adler, Noleen Köhler, Pan Peng
We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that…
Tree-width for first order formulae
Isolde Adler, Mark Weyer
We introduce tree-width for first order formulae ϕ, fotw(ϕ). We show that computing fotw is fixed-parameter tractable with parameter fotw. Moreover, we show that on classes of form…
A note on clique-width and tree-width for structures
Hans Adler, Isolde Adler
We give a simple proof that the straightforward generalisation of clique-width to arbitrary structures can be unbounded on structures of bounded tree-width. This can be corrected b…