Zobrazeno 1 - 10
of 278
pro vyhledávání: '"Ludwig Staiger"'
Autor:
Ludwig Staiger
Publikováno v:
Logical Methods in Computer Science, Vol Volume 16, Issue 2 (2020)
Using an iterative tree construction we show that for simple computable subsets of the Cantor space Hausdorff, constructive and computable dimensions might be incomputable.
Externí odkaz:
https://doaj.org/article/4b7741fa7fc14527a966268ecedee04b
Autor:
Ludwig Staiger
Publikováno v:
Axioms, Vol 10, Iss 4, p 306 (2021)
A quasiperiod of a finite or infinite string is a word whose occurrences cover every part of the string. An infinite string is referred to as quasiperiodic if it has a quasiperiod. We present a characterisation of the set of infinite strings having a
Externí odkaz:
https://doaj.org/article/61c8a2c67bb849009e63820522667845
Autor:
Ludwig Staiger, Ziyuan Gao, Frank Stephan, Sanjay Jain, Karen Frilya Celine, Cristian S. Calude
Publikováno v:
Theoretical Computer Science. 894:31-49
In this paper we study various notions of bi-immunity over alphabets with b ≥ 2 elements and recursive transformations between sequences on different alphabets which preserve them. Furthermore, we extend the study from sequences bounded by a consta
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1e35f85bb2a94ea386ad5a17fe16e4b1
https://doi.org/10.1016/j.tcs.2021.09.005
https://doi.org/10.1016/j.tcs.2021.09.005
Autor:
Helmut Jürgensen, Ludwig Staiger
Publikováno v:
Theoretical Computer Science. 892:25-47
Solid codes provide outstanding fault-tolerance when used for information transmission through a noisy channel involving not only symbol substitutions, but also synchronisation errors and black-outs. In this paper we provide an automaton theoretic ch
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1e1df059beeaf89ad96b3e07eadc78a0
https://doi.org/10.1016/j.tcs.2021.09.007
https://doi.org/10.1016/j.tcs.2021.09.007
Publikováno v:
Theoretical Computer Science. 952:113819
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f7310477bc1e4b66316a2dbcfc779125
https://doi.org/10.1016/j.tcs.2023.113819
https://doi.org/10.1016/j.tcs.2023.113819
Autor:
Ronny Polley, Ludwig Staiger
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 31, Iss Proc. DCFS 2010, Pp 169-176 (2010)
We provide an exact estimate on the maximal subword complexity for quasiperiodic infinite words. To this end we give a representation of the set of finite and of infinite words having a certain quasiperiod q via a finite language derived from q. It i
Externí odkaz:
https://doaj.org/article/55b27a4b4166424c956d16bc1a680803
Autor:
Ludwig Staiger
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 17 no. 1, Iss Automata, Logic and Semantics (2015)
Automata, Logic and Semantics
Externí odkaz:
https://doaj.org/article/b594358a6cd14519afc05dbb615fdb96
Publikováno v:
Theoretical Computer Science. 679:145-161
The space of one-sided infinite words plays a crucial rle in several parts of Theoretical Computer Science. Usually, it is convenient to regard this space as a metric space, the Cantor space. It turned out that for several purposes topologies other t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::cffc6ae6d73414369f6fba52d743cff7
https://doi.org/10.1016/j.tcs.2016.10.003
https://doi.org/10.1016/j.tcs.2016.10.003
Autor:
Cristian S. Calude, Ludwig Staiger
Publikováno v:
Theory of Computing Systems. 62:1573-1585
We survey the relations between four classes of real numbers: Liouville numbers, computable reals, Borel absolutely-normal numbers and Martin-Lof random reals. Expansions of reals play an important role in our analysis. The paper refers to the origin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::408bc587857f92e046d22e354ccc4721
https://doi.org/10.1007/s00224-017-9767-8
https://doi.org/10.1007/s00224-017-9767-8
Autor:
Ludwig Staiger
Publikováno v:
Descriptional Complexity of Formal Systems ISBN: 9783030625351
DCFS
DCFS
It is shown that, for every length \(l\ge 3\), a quasiperiod of the form \(a^{n}ba^{n}\) (or \(a^{n}bba^{n}\) if l is even) generates the largest language Q of words having this word as quasiperiod. As a means of comparison we use the growth of the f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c341b1f71ea430be7f28d9cfca4ca33b
https://doi.org/10.1007/978-3-030-62536-8_18
https://doi.org/10.1007/978-3-030-62536-8_18
