12 citations · 27 across the 18 of their papers we have counts for
19 papers
Normal Sequences with Non-Maximal Automatic Complexity
Liam Jordon, Philippe Moser
This paper examines Automatic Complexity, a complexity notion introduced by Shallit and Wang in 2001. We demonstrate that there exists a normal sequence such that an…
A Normal Sequence Compressed by PPM but not by Lempel-Ziv 78
Liam Jordon, Philippe Moser
In this paper we compare the difference in performance of two of the Prediction by Partial Matching (PPM) family of compressors (PPM and the original Bounded PPM algorithm) and…
Pebble-Depth
Liam Jordon, Philippe Moser
In this paper we introduce a new formulation of Bennett's logical depth based on pebble transducers. This notion is defined based on the difference between the minimal length descr…
Pushdown and Lempel-Ziv Depth
Liam Jordon, Philippe Moser
This paper expands upon existing and introduces new formulations of Bennett's logical depth. In previously published work by Jordon and Moser, notions of finite-state depth and pus…
Polynomial Depth, Highness and Lowness for E
Philippe Moser
We study the relations between the notions of highness, lowness and logical depth in the setting of complexity theory. We introduce a new notion of polylog depth based on time boun…
Depth, Highness and DNR degrees
Philippe Moser, Frank Stephan
We study Bennett deep sequences in the context of recursion theory; in particular we investigate the notions of O(1)-deepK, O(1)-deepC , order-deep K and order-deep C sequences. Ou…