Zobrazeno 1 - 10
of 180
pro vyhledávání: '"Bjørn Kjos-Hanssen"'
Autor:
Johanna N. Y. Franklin
Publikováno v:
The Bulletin of Symbolic Logic. 19:115-118
Autor:
Bjørn Kjos-Hanssen
Publikováno v:
Forum of Mathematics, Sigma, Vol 9 (2021)
Shallit and Wang showed that the automatic complexity $A(x)$ satisfies $A(x)\ge n/13$ for almost all $x\in {\{\mathtt {0},\mathtt {1}\}}^n$ . They also stated that Holger Petersen had informed them that the constant $13$ can be reduced to
Externí odkaz:
https://doaj.org/article/0255db405b4b41148c6061444c212f85
Publikováno v:
Annals of Mathematics and Artificial Intelligence. 90:93-105
Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$ denote the set of words of length $n$. We give a quadratic lower bound on the VC dimension of \[ NFA_
Autor:
Bjørn Kjos-Hanssen
Publikováno v:
Discrete Applied Mathematics. 289:446-454
For a complexity function $C$, the lower and upper $C$-complexity rates of an infinite word $\mathbf{x}$ are \[ \underline{C}(\mathbf x)=\liminf_{n\to\infty} \frac{C(\mathbf{x}\upharpoonright n)}n,\quad \overline{C}(\mathbf x)=\limsup_{n\to\infty} \f
Autor:
Bjørn Kjos-Hanssen, David J. Webb
Publikováno v:
Revolutions and Revelations in Computability ISBN: 9783031087394
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a825b2675589a3eb01ec2018f5d117b8
https://doi.org/10.1007/978-3-031-08740-0_13
https://doi.org/10.1007/978-3-031-08740-0_13
Publikováno v:
Logical Foundations of Computer Science ISBN: 9783030930998
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::958ac9f7ae0fca8b4ae9b42625d203a0
https://doi.org/10.1007/978-3-030-93100-1_8
https://doi.org/10.1007/978-3-030-93100-1_8
Publikováno v:
Logical Methods in Computer Science, Vol Volume 10, Issue 4 (2014)
We study Doob's martingale convergence theorem for computable continuous time martingales on Brownian motion, in the context of algorithmic randomness. A characterization of the class of sample points for which the theorem holds is given. Such points
Externí odkaz:
https://doaj.org/article/40ad0e55687f4ff6a0c32c93a0aea240
Autor:
Bjørn Kjos-Hanssen, Lu Liu
Publikováno v:
European Journal of Mathematics. 6:1438-1451
The tree forcing method of Liu enables the cone avoiding of bounded enumeration of a given tree, within subsets or co-subsets of an arbitrary given set, provided the given tree does not admit computable bounded enumeration. Using this result, he sett
Autor:
Bjørn Kjos-Hanssen
Automatic complexity is a computable and visual form of Kolmogorov complexity. Introduced by Shallit and Wang in 2001, it replaces Turing machines by finite automata, and has connections to normalized information distance, logical depth, and linear d
Autor:
Bjørn Kjos-Hanssen, David J. Webb
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030800482
CiE
CiE
We show that the (truth-table) Medvedev degree KLR of Kolmogorov–Loveland randomness coincides with that of Martin-Lof randomness, MLR, answering a question of Miyabe. Next, an analogue of complex packing dimension is studied which gives rise to a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b817a440b8a0c705e9c50ea9aced1969
https://doi.org/10.1007/978-3-030-80049-9_45
https://doi.org/10.1007/978-3-030-80049-9_45