| ||||||||
Ludwig Staiger's Publications |
Reports of the Department of Mathematics and Computer Science
Reports of the Institute of Computer Science (until 2006)
Reports of the Institute of Computer Science (from 2007)
Reports of the Theoretical Computer Science Group
CDMTCS-Reports of the Theoretical Computer Science Group
The Kolmogorov Complexity of Infinite Objects
Descriptional Complexity of Formal Systems, 7th Workshop,
Como, Italy, June 30 - July 2, 2005
appeared as ECCC Report TR06-070
On the Computation of Hausdorff Dimension
at Centre for
Discrete Mathematics and Theoretical Computer Science, Auckland
(New Zealand), 7. August 1998
Maß, Kategorie und Dimension im Sequenz-Kalkül.
at Kurt-Gödel-Gesellschaft,
Wien, 24. November 1997
Announcment
and Abstract gzipped
.ps-file (219k)
Weighted Finite Automata and Metrics in Cantor Space
Journal of Automata, Languages and Combinatorics, Vol. 8 (2003), No. 2, 353 - 360.
CDMTCS-report 196 .pdf-file
The Entropy of Lukasiewicz Languages
in: Developments in
Language Theory,
(W. Kuich, G. Rozenberg and A. Salomaa Eds.)
Lecture Notes in Comput. Sci. No. 2295, Springer-Verlag, Berlin 2002,
pp. 155 - 165.
Abstract
Topologies for the Set of Disjunctive
ω-words
in: Words, Semigroups & Transductions,
Festschrift in Honor of Gabriel Thierrin,
(M. Ito, Gh. Paun
and Sh. Yu, eds.),
World Scientific, Singapore 2001, pp. 421 - 430.
Preprint
01-15
How Large is the Set of Disjunctive Sequences?
Journal of Universal Computer Science, Vol. 8 (2002), No. 2, 348 - 362.
Preliminary version in:
Combinatorics, Computability, Logic, Proceedings of
DMTCS'01
(C.S. Calude, M.J. Dinneen, and S. Sburlan, eds.),
Discrete Mathematics and Theoretical Computer Science,
Springer-Verlag, London 2001, pp. 215 - 225.
CDMTCS-report 175 .pdf-file (221k)
with Rudolf Freund
Acceptance of
ω-Languages by Communicating Deterministic Turing~Machines,
in: Words, Sequences, Grammars, Languages: where Biology,
Computer
Science, Linguistics and Mathematics Meet, Vol I.
(C. Martin-Vide and V. Mitrana Eds.), Kluwer, Dordrecht 2000, pp. 115 - 125.
.ps-file (308k)
On the Power of Reading the Whole Infinite Input Tape,
in:
Finite
Versus Infinite: Contributions to an Eternal Dilemma.
(C. S. Calude,
and Gh. Paun, eds.)
Discrete Mathematics and Theoretical Computer
Science,
Springer-Verlag, London 2000, pp. 335 - 348.
Preprint
99-15
with Helmut
Jürgensen
Finite Automata Encoding Geometric Figures,
in: Automata Implementation, (O. Boldt and H. Jürgensen, eds.)
Proc. 4th International Workshop on Implementing Automata Potsdam 1999,
Lecture Notes in Comput. Sci. No. 2214, Springer-Verlag, Berlin 2001, pp. 101 - 108.
.ps-file (298k)
How much can you win when your adversary is handicapped?
in:: Numbers, Information and Complexity,
(I. Althöfer et al., eds.),
Kluwer, Dordrecht 2000, pp. 403 - 412.
gzipped
.ps-file (213k)
with Henning
Fernau and Klaus
Reinhardt
Decidability of Code Properties,
in:
Proc. "Developments in
Language Theory IV" (G. Rozenberg and W. Thomas,
eds.),
World Scientific, Singapore 2000, pp. 153 - 163.
gzipped
.ps-file (101k) Full version (174k)
The Kolmogorov Complexity of Real Numbers,
Theoret. Comput. Sci., Vol. 284 (2002), 455 - 466.
Preliminary version in:
Proc. "Fundamentals of Computation Theory" (G. Ciobanu and
Gh. Paun, eds.)
Lecture Notes in Comput. Sci. No. 1684, Springer-Verlag, Berlin 1999, pp. 536 - 546.
Preprint 99-14
The Hausdorff Measure of Regular ω-languages is Computable,
Bull. EATCS 66 (1998), 178 - 182.
Abstract and .ps-file (158k)
with Henning
Fernau
Iterated Function Systems and Control Languages,
Information and Computation, Vol. 168 (2001), 125 - 143.
Preliminary version in:
Proc. MFCS'1998 (L. Brim, J. Gruska
and J. Zlatuska, Eds.),
Lecture Notes in Comput. Sci. No. 1450,
Springer-Verlag, Berlin 1998, 740 - 750.
Abstract Full version (663k)
A tight upper bound on Kolmogorov complexity and uniformly optimal
prediction,
Theory of Computing Systems, Vol. 31 (1998), 215 -
229.
Abstract and gzipped .ps-file [TR 95-03] (63k)
Rich ω-Words and Monadic Second-Order Arithmetic.
in: Proceedings of
the conference Computer Science Logic'97,
Lecture Notes in
Comput. Sci. No. 1414, Springer-Verlag, Berlin 1998, 478 - 490.
Abstract
gzipped .ps-file (83k)
ω-Languages.
in: Handbook of Formal Languages, (G. Rozenberg and A. Salomaa Eds.),
Springer-Verlag, Berlin 1997, Vol. 3, 339-387.
Abstract
gzipped .ps-file (189k)
with Oded Maler
On Syntactic Congruences for ω-languages.
Theoret. Comput. Sci., Vol. 183 (1997), No. 1, 93-112.
Abstract and .pdf-file (252k)
Preliminary version in:
Proc. STACS '93 (P. Enjalbert, A. Finkel and K.W. Wagner Eds.),
Lecture Notes in Comput. Sci. No. 665, Springer-Verlag, Berlin 1993, 586-594.
AMS Classification and Zbl-Abstract
On ω-power languages,
in: New Trends in Formal Languages, Control, Cooperation, and Combinatorics,
(Gh. Paun and A. Salomaa, Eds.),
Lecture Notes in Comput. Sci. No. 1218,
Springer-Verlag, Berlin 1997, 377-393.
gzipped .ps-file (113k)
with Igor Litovsky
Finite acceptance of infinite words.
Theoret. Comput. Sci., Vol. 174 (1997), No. 1-2, 1-21.
Abstract and gzipped .ps-file [TR 94-17] (72k)
Preliminary version in:
Developments in Language Theory II;
At The Crossroads of Mathematics, Computer Science and Biology
(J. Dassow, G. Rozenberg and A. Salomaa, Eds.),
World Scientific, Singapore 1996, 360 - 369.
gzipped .ps-file (77k)
with Rudolf Freund
Numbers defined by Turing machines.
Collegium Logicum (Annals of the Kurt-Gödel-Society), Vol. 2,
Springer-Verlag, Wien New York 1996, 118-137.
AMS Classification and Zbl-Abstract
and gzipped .ps-file (93k)
Codes, simplifying words, and open set condition.
in: Mathematical Linguistics and Related Topics (Gh. Paun, Ed.),
The Publishing House of the Romanian Academy of Sciences, Bucharest 1995, 308-312.
also in: Information Process. Lett. Vol. 58 (1996), 297-301.
gzipped .ps-file (74k)
with Michael Kaplan
Low-degree Mattson-Solomon polynomials.
Atti Sem. Mat. Fis. Univ. Modena, Vol. 43 (1995), 265-272.
AMS Classification and Zbl-Abstract, Abstract and gzipped .ps-file (49k)
with Helmut Jürgensen
Local Hausdorff dimension.
Acta Informatica, Vol. 32 (1995), No. 5, 491-507.
AMS Classification and Zbl-Abstract
with Wolfgang Merzenich
Fractals, dimension, and formal languages.
RAIRO Informatique théorique et Applications, Vol. 28 (1994), No. 3-4, 361-386.
Preliminary version in:
Developments in Language Theory;
At The Crossroads of Mathematics, Computer Science and Biology
(G. Rozenberg and A. Salomaa, Eds.),
World Scientific, Singapore 1994, 262 - 277.
gzipped .ps-file (76k)
with Henning Fernau
Valuations and unambiguity of languages, with an application to fractal geometry.
in: Proc. ICALP'94 (S. Abiteboul and E. Shamir, Eds.),
Lecture Notes in Comput. Sci. No. 820, Springer-Verlag, Berlin 1994, 11-22.
.ps-file (367k)
Extended version:
Abstract and gzipped .ps-file [TR 94-22] (143k)
with Jeanne Devolder, Michel Latteux and Igor Litovsky
Codes and infinite words.
Acta Cybernetica, Vol. 11 (1994), No. 4, 241-256.
Abstract
Kolmogorov complexity and Hausdorff dimension.
Information and Computation, Vol. 103 (1993), No. 2, 159-194.
AMS Classification and Zbl-Abstract
Preliminary version in:
Proc. Fundamentals of Computation Theory (J. Csirik, J. Demetrovics
and F. Gécseg Eds.),
Lecture Notes in Comput. Sci. No. 380, Springer-Verlag, Berlin 1989, 334-343.
gzipped .ps-file (83k)
Recursive automata on infinite words.
in: Proc. STACS '93 (P. Enjalbert, A. Finkel and K.W. Wagner Eds.),
Lecture Notes in Comput. Sci. No. 665, Springer-Verlag, Berlin 1993, 629-639.
AMS Classification and Zbl-Abstract and gzipped .ps-file (75k)
with Klaus Wagner
Rekursive Folgenmengen I.
Zeitschr. Math. Logik Grundlag. Math., Vol. 24 (1978), No. 6, 523-538.
AMS Classification and Zbl-Number
English version in: Proc. Fundamentals of Computation Theory (M. Karpinski, ed.),
Lecture Notes in Comput. Sci. No. 56, Springer-Verlag, Berlin 1977, 532-537.
Complexity and entropy.
in: Proc. MFCS'1981 (J. Gruska and M. Chytil, Eds.),
Lecture Notes in Comput. Sci. No. 118, Springer-Verlag, Berlin 1981, 508-514.
AMS Classification and Zbl-Number
Finite-state ω-languages.
J. Comput. Syst. Sci., Vol. 27 (1983), 434-448.
AMS Classification and Zbl-Abstract
Subspaces of GF(q)ω and convolutional codes.
Inf. Control, Vol. 59 (1983), 148-183 (1983).
AMS Classification and Zbl-Abstract
A short version appeared in:
Proc. 6th Intern. Symp. on Inform. Theory, Tashkent 1984, Part 2,
Tashkent-Moscow, pp. 251 - 253.
Projection lemmas for ω-languages.
Theor. Comput. Sci., Vol. 32 (1984), 331-337 .
AMS Classification and Zbl-Abstract
with Cristian Calude and Ion Chitescu
P. Martin-Löf tests: Representability and embeddability.
Rev. Roumaine Math. Pures Appl., Vol. 30 (1985), No. 9, 719-732.
AMS Classification and Zbl-Abstract
with Werner Nehrlich
The centers of context-sensitive languages.
in: Proc. MFCS'1986 (J. Gruska, B. Rovan and J. Wiedermann, Eds.),
Lecture Notes in Comput. Sci. No. 233, Springer-Verlag, Berlin 1986, 594-601.
AMS Classification and Zbl-Abstract
On infinitary finite length codes.
RAIRO Informatique théorique et Applications, Vol. 21 (1986), No. 2, 147-173.
AMS Classification and Zbl-Abstract
Why are serial convolutional encoders catastrophic?
J. Inform. Process. Cybernetics EIK, Vol. 23 (1987), No. 12, 609-614.
AMS Classification and Zbl-Abstract
On the square-root bound for QR-codes.
J. of Geometry, Vol. 31 (1988), No. 1/2, 172-178.
AMS Classification and Zbl-Abstract
Ein Satz über die Entropie von Untermonoiden.
Theoret. Comput. Sci., Vol. 61 (1988), No. (2,3), 279-282.
AMS Classification and Zbl-Abstract
Quadtrees and the Hausdorff dimension of pictures.
in: ``GEOBILD 89'', Proc. 4th Workshop on Geometrical
Problems
of Image Processing, (A. Hübler, W. Nagel, B. D. Ripley
and G. Werner, eds.),
Mathematical Research No. 51, Akademie-Verlag,
Berlin 1989, 173-178.
.ps-file (69k)
Combinatorial properties of the Hausdorff dimension.
J. Statist. Plann. Inference, Vol. 23 (1989), No. 1, 95-100.
AMS Classification and
Zbl-Abstract
On codes having dual distance d' < k.
J. Inform. Process. Cybernetics EIK, Vol. 27 (1991), No. 7, 377-386.
AMS Classification and
Zbl-Abstract gzipped
.ps-file (54 k)
Hausdorff dimension of constructively specified sets and applications to image processing.
in: Topology, Measures, and Fractals (Ch. Bandt, J. Flachsmeyer and H. Haase Eds.),
Mathematical Research No. 66, Akademie-Verlag, Berlin 1992, 109-120.
AMS Classification and Zbl-Abstract
L. Staiger, December 12, 1995
Last modified: Fri Jun 2 18:19:25 MEST 2006