On Oscillation-free epsilon-random Sequences II

Mielke, Jöran; Staiger, Ludwig

doi:10.4230/OASIcs.CCA.2009.2269

Document

On Oscillation-free epsilon-random Sequences II

Authors Jöran Mielke, Ludwig Staiger

Part of: Volume: 6th International Conference on Computability and Complexity in Analysis (CCA'09) (CCA 2009)
Part of: Series: Open Access Series in Informatics (OASIcs)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2009-11-25

PDF

File

PDF

OASIcs.CCA.2009.2269.pdf

Filesize: 374 kB
11 pages

Document Identifiers

DOI: 10.4230/OASIcs.CCA.2009.2269
URN: urn:nbn:de:0030-drops-22698

Subject Classification

Keywords

Omega-words
partial randomness
a priori complexity
monotone complexity

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

It has been shown (see (Staiger, 2008)), that there are strongly \textsc{Martin-L\"of}-$\varepsilon$-random $\omega$-words that behave in terms of complexity like random $\omega$-words. That is, in particular, the \emph{a priori} complexity of these $\varepsilon$-random $\omega$-words is bounded from below and above by linear functions with the same slope $\varepsilon$. In this paper we will study the set of these $\omega$-words in terms of \textsc{Hausdorff} measure and dimension. 

Additionally we find upper bounds on \emph{a priori} complexity, monotone and simple complexity for a certain class of $\omega$-power languages.

Cite As Get BibTex

Jöran Mielke and Ludwig Staiger. On Oscillation-free epsilon-random Sequences II. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 173-184, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/OASIcs.CCA.2009.2269

Author Details

Jöran Mielke

Ludwig Staiger

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail