Publications by Dirk Nowotka

• 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 Repetition-free Words on Small Alphabets
  Information Processing Letters, 110:591-595, 2010. (with T. Harju)
• Weinbaum Factorizations of Primitive Words
  Izvestiya VUZ. Matematika (Известия высших учебных заведений. Математка), (1):21-33, 2010. (with V. Diekert and T. Harju)
• Maximal Intersection Queries in Randomized Input Models
  Theory of Computing Systems, 46(1):104-119, 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):606-608, 2008. (with S. Göller)
• Unbordered Factors and Lyndon Words
  Discrete Mathematics, 308(11):2261-2264, 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):165-171, 2006. (with T. Harju)
• On Unique Factorizations of Primitive Words
  Theoretical Computer Science, 356(1-2):186-189, 2006. (with T. Harju)
• Counting Bordered and Primitive Words with a Fixed Weight
  Theoretical Computer Science, 340(2):273-279, 2005. (with T. Harju)
• On the Equation x^k = z₁^k₁z₂^k₂...z_n^k_n in a Free Semigroup
  Theoretical Computer Science, 330(1):117-121, 2005. (with T. Harju)
• A Characterization of Periodicity of Bi-infinite Words
  Theoretical Computer Science, 347(1-2):419-422, 2005. (with T. Harju and A. Lepistö)
• The Equation xⁱ = y^jz^k in a Free Semigroup
  Semigroup Forum, 68(3):488-490, 2004. (with T. Harju)
• Border Correlation of Binary Words
  Journal of Combinatorial Theory, Series A, 108(2):331-341, 2004. (with T. Harju)
• Minimal Duval Extensions
  International Journal of Foundations of Computer Science, 15(2):349-354, 2004. (with T. Harju)
• On the Independence of Equations in Three Variables
  Theoretical Computer Science, 307(1):139-172, 2003. (with T. Harju)
• Density of Critical Factorizations
  Theoretical Informatics and Applications, 36(3):315-327, 2002. (with T. Harju)

• The Ehrenfeucht-Silberger Problem
  Automata, Languages and Programming (ICALP), Rhodes, 2009, volume 5555 of Lecture Notes in Computer Science, pages 537-548, Springer-Verlag, 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 408-418, Springer-Verlag, 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, Springer-Verlag, 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, Springer-Verlag, Berlin, 2007. (with Y. Lifshits)
  This contribution received the award Best Paper in Applications/Technology Track of CSR 2007.
• Height-Deterministic Pushdown Automata
  International Symposium on Mathematical Foundations of Computer Science (MFCS), Český Krumlov, 2007, volume 4708 of Lecture Notes in Computer Science, pages 125-134, Springer-Verlag, Berlin, 2007. (with J. Srba)
• Verification in the Design Process of Large Real-Time 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 392-397, 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 294-304, Springer-Verlag, 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 316-324, Springer-Verlag, 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 Logic-based 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 77-93, Research Studies Press Ltd., Baldock, 2000. (with M. Benini and C. Pulley)
• Program Abstraction in a Higher-Order 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 33-48, Springer-Verlag, 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)

• Proceedings of Developments in Language Theorie (DLT) 2009
  volume 5583 of Lecture Notes in Computer Science, Springer-Verlag, 2009. (with V. Diekert)

• Periodicity and Unbordered Factors of Words
  Number 50 of TUCS Dissertations, June 2004.
  Turku Centre of Computer Science (TUCS) and Department of Mathematics, University of Turku, Finland.

• Formale Methoden in der Softwareentwicklung
  ATZelektronik, 3(4):24-27, Vieweg Verlag, 2008. [dt] [eng]
• Binary Words with Few Squares
  Bulletin of the EATCS, 89:164-166, June 2006. (with T. Harju)
• Periodicity and Unbordered Segments of Words
  Bulletin of the EATCS, 80:162-167, June 2003. (with T. Harju)

• A091838
• A099766