Publications by Dirk Nowotka
Journals
 The Number of Positions Starting a Square in Binary Words
Electronic Journal of Combinatorics, accepted, 2010.
(with T. Harju and T. Kärki)
 On
the Relation between Periodicity and Unbordered Factors of Finite
Words
International Journal of Foundations of Computer Science, accepted, 2010.
(with Š. Holub)
 Cyclically Repetitionfree Words on Small Alphabets
Information Processing Letters, 110:591595, 2010.
(with T. Harju)
 Weinbaum
Factorizations of Primitive Words
Izvestiya VUZ. Matematika (Известия высших учебных заведений.
Математка),
(1):2133, 2010. (with V. Diekert and T. Harju)
 Maximal Intersection Queries in Randomized Input Models
Theory of Computing Systems, 46(1):104119, 2010. (with B. Hoffmann, M. Lifshits, and Y. Lifshits)
 Bordered Conjugates of Words over Large Alphabets
Electronic Journal of Combinatorics, 15(1):N41, 2008.
(with T. Harju)
 A Note on an Extension of PDL
Journal of Applied Logic, 6(4):606608, 2008. (with S. Göller)
 Unbordered
Factors and Lyndon Words
Discrete Mathematics, 308(11):22612264, 2008. (with J.P. Duval and T.
Harju)
 Periodicity and
Unbordered Words: A Proof of the Extended Duval Conjecture
Journal of the ACM, 54(4):20, 2007. (with T. Harju)
 Periods in
Word Extensions
Acta Informatica, 43(3):165171, 2006. (with T. Harju)
 On Unique
Factorizations of Primitive Words
Theoretical Computer Science, 356(12):186189, 2006. (with
T. Harju)
 Counting
Bordered and Primitive Words with a Fixed Weight
Theoretical Computer Science, 340(2):273279, 2005. (with T.
Harju)
 On the Equation x^{k}
= z_{1}^{k1}z_{2}^{k2}...z_{n}^{kn}
in a Free Semigroup
Theoretical Computer Science, 330(1):117121, 2005. (with T.
Harju)
 A
Characterization of Periodicity of Biinfinite Words
Theoretical Computer Science, 347(12):419422, 2005. (with
T. Harju and A. Lepistö)
 The
Equation x^{i} = y^{j}z^{k} in
a Free Semigroup
Semigroup Forum, 68(3):488490, 2004. (with T. Harju)
 Border
Correlation of Binary Words
Journal of Combinatorial Theory, Series A, 108(2):331341,
2004. (with T. Harju)
 Minimal Duval
Extensions
International Journal of Foundations of Computer Science,
15(2):349354, 2004. (with T. Harju)
 On the
Independence of Equations in Three Variables
Theoretical Computer Science, 307(1):139172, 2003. (with T.
Harju)
 Density of
Critical Factorizations
Theoretical Informatics and Applications, 36(3):315327,
2002. (with T. Harju)
Conferences

The EhrenfeuchtSilberger Problem
Automata, Languages and Programming (ICALP), Rhodes, 2009,
volume 5555 of Lecture Notes in Computer Science,
pages 537548, SpringerVerlag, Berlin, 2009.
(with Š. Holub)
(This solves a longstanding problem by Ehrenfeucht and Silberger
about the relation between the period of a word and its longest
unbordered factor.)
 On
the Relation between Periodicity and Unbordered Factors of Finite
Words
Developments in Language Theory (DLT), Kyoto, 2008,
volume 5257 of Lecture Notes in Computer Science,
pages 408418, SpringerVerlag, Berlin, 2008.
(with Š. Holub)
 Maximal Intersection
Queries in Randomized Graph Models
In V. Diekert, M. Volkov, and A. Voronkov (eds), International
Computer Science Symposium in Russia (CSR), Ekaterinburg, 2007,
volume 4649 of Lecture Notes in Computer Science,
SpringerVerlag, Berlin, 2007. (with B. Hoffmann and Y. Lifshits)
 Estimation of the
Click Volume by Large Scale Regression Analysis
In V. Diekert, M. Volkov, and A. Voronkov (eds), International
Computer Science Symposium in Russia (CSR), Ekaterinburg, 2007,
volume 4649 of Lecture Notes in Computer Science,
SpringerVerlag, Berlin, 2007. (with Y. Lifshits)
This contribution received the award Best Paper in Applications/Technology
Track of CSR 2007.
 HeightDeterministic
Pushdown Automata
International Symposium on Mathematical Foundations of Computer
Science (MFCS),
Český Krumlov, 2007, volume 4708 of
Lecture Notes in Computer Science, pages 125134, SpringerVerlag,
Berlin, 2007. (with J. Srba)
 Verification
in the Design Process of Large RealTime Systems: A Case Study
In E. Plödereder, H. B. Keller, P. Dencker, and M. Tonndorf (eds),
Automotive  Safety & Security 2006  Sicherheit und
Zuverlässigkeit für automobile Informationstechnik,
Stuttgart, Shaker Verlag, Aachen, 2006. (with P. Montag and P. Levi)
 Factorizations
of Cyclic Words
Workshop on Words and Automata (WoWA) at the International
Computer Science Symposium in Russia (CSR), St. Petersburg, 2006. (with
V. Diekert and T. Harju)
 About Duval
Extensions
In T. Harju and J. Karhumäki (eds), WORDS, Turku, 2003,
number 27 of TUCS General Publications, pages 392397, Turku Centre of
Computer Science, Turku, 2003. (with T. Harju)
 Periodicity
and Unbordered Words
In V. Diekert and M. Habib (eds), International Symposium on
Theoretical Aspects of Computer Science (STACS), Montpellier, 2004,
volume 2996 of Lecture Notes in Computer Science, pages
294304, SpringerVerlag, Berlin, 2004. (with T. Harju)
 About
Duval's Conjecture
In Z. Esik and Z. Fülöp (eds), Developments in Language
Theory (DLT), Szeged, 2003, volume 2710 of Lecture Notes in
Computer Science, pages 316324, SpringerVerlag, Berlin, 2003.
(with T. Harju)
 Density of
Critical Factorizations
Workshop on Automata, Words, and Logic, Turku, 2002. (with
T. Harju)
 On the
Independence of Equations in Three Variables
WORDS, Palermo, 2001. (with T. Harju)
 Constructive
Methods in Automatic Analysis of Correctness Proofs (poster)
9th International Workshop on Logicbased Program Synthesis and
Transformation (LoPSTr), Venice, 1999. (with A. Avellone and M.
Benini)
 Computer
Arithmetic: Logic, Calculation, and Rewriting
In D. Gabbay and
M. de Rijke (eds),
Frontiers of Combining Systems 2 (FroCS), Amsterdam, 1998,
volume 7 of Studies in Logic and Computation, pages 7793,
Research Studies Press Ltd., Baldock, 2000. (with M. Benini and C.
Pulley)
 Program
Abstraction in a HigherOrder Logic Framework
In J. Grundy and
M. Newey (eds),
Theorem Proving in Higher Order Logics (TPHOLs), Canberra,
1998, volume 1479 of Lecture Notes in Computer Science, pages
3348, SpringerVerlag, Berlin, 1998. (with M. Benini and S. Kalvala)
 Holly  An Approach to
Object Code Verification
5th Annual Automated Reasoning Workshop (ARW) at the 14th
British Colloquium for Theoretical Computer Science (BCTCS), St.
Andrews, 1998. (with M. Benini and S. Kalvala)
Book
PhD Thesis
Other Publications
OnLine Encyclopedia of Integer Sequences
(OEIS)
This page was last updated on December 7, 2010.