Fundamentals of Computing and Discrete Mathematics

The journal papers of the Words and Automata Group 2002 –

  1. A. Okhotin, C. Reitwießner, Conjunctive grammars with restricted disjunction, Theoretical Computer Science, 411:26-28 (2010), 2559-2571.
  2. T. Lehtinen, A. Okhotin, Boolean grammars and gsm mappings, International Journal of Foundations of Computer Science, 21:5 (2010), 799-815.
  3. A. Jeż, A. Okhotin, Univariate equations over sets of natural numbers, Fundamenta Informaticae, 103 (2010), to appear.
  4. A. Jeż, A. Okhotin, Conjunctive grammars over a unary alphabet: undecidability and unbounded growth, Theory of Computing Systems,46:1 (2010), 27-58.
  5. A. Okhotin. Decision problems for language equations, Journal of Computer and System Sciences, 76:3-4 (2010), 251-266.
  6. Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Abelian Complexity in Minimal Subshifts. To appear in J. Lond. Math. Soc.
  7. Kalle Saari. Everywhere α-Repetitive Sequences and Sturmian Words. Europ. J. Combin., 31(1), 177-192, 2010.
  8. Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Balance and Abelian Complexity of the Tribonacci Word. Adv. Appl. Math. 45(2), 212--231, 2010.
  9. Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Standard Factors of Sturmian Words. RAIRO-Theor. Inform. Appl. 44(1), 159-174, 2010.
  10. Vesa Halava, Tero Harju and Tomi Kärki. On the number of squares in partial words, RAIRO Theoret. Inf. Applic. 44 (2010), 125-138.
  11. Robert Brijder, Mark Daley, Tero Harju, Natasha Jonoska, Ion Petre and Grzegorz Rozenberg. Computational gene assembly in ciliates, to appear in Handbook of Natural Computing (Th.Bäck, J.Kok and G.Rozenberg (eds.)), Springer-Verlag 2010.
  12. Tero Harju and Dirk Nowotka. Cyclically repetition-free words on small alphabets, Inf. Processing Letters 110 (2010), 591-595.
  13. Volker Diekert, Tero Harju and Dirk Nowotka. Weinbaum factorizations of primitive words (Russian), Izvestiya Vuzov. Matematika 2010 (1), 21-33; In English: Russian Mathematics (Iz VUZ) 54 (1), 16-25.
  14. Juha Honkala. A characterization of rational D0L power series. Acta Informatica (to appear).
  15. Juhani Karhumäki, Aleksi Saarela. Noneffective regularity of equality languages and bounded delay morphisms. Discret. Math. & Theoret Comput Sci. (to appear)
  16. Juhani Karhumäki, Yuri Lifshits, Wojciech Rytter. Tiling periodicity. Discret. Math. & Theoret. Comput. Sci. 12(2) (2010), 237-248.
  17. Juhani Karhumäki, Michal Kunc and Alexander Okhotin. Computational power of two stacks with restricted communication. Information and Computation 208 (2010) 1060-1089. doi:10.1016/j.ic.2009.07.001
  18. Paul Bell, Vesa Halava, and Mika Hirvensalo: On the Joint Spectral Radius for Bounded Matrix Languages. LNCS 6227, (2010) 91-103.
  19. Mika Hirvensalo, Juhani Karhumäki, and Alexander Rabinovich. Computing Partial Information out of Intractable: Powers of Algebraic Numbers as an Example. Journal of Number Theory 130, (2010) 232-253.
  20. Oscar Ibarra, Juhani Karhumäki and Alexander Okhotin. On stateless multihead automata: hierarchies and the emptiness problem. Theor. Comput. Sci. 411 (2010) 581-593.
  21. A. Okhotin, On the state complexity of scattered substrings and superstrings, Fundamenta Informaticae, 99:3 (2010), 325-338.
  22. Vesa Halava, Tero Harju and Tomi Kärki. On the number of squares in partial words. RAIRO Inform. Théor. Appl. 44 (2010) 125-138.
  23. Volker Diekert, Tero Harju and Dirk Nowotka. Weinbaum factorizations of primitive words (Russian). Izvestiya Vuzov. Matematika 2010 (1) 21-33.
  24. Mari Huova. A Note on Defect Theorems for 2-Dimensional Words and Trees. Journal of Automata, Languages and Combinatorics vol. 14 (2009) 3/4, 203-209.
  25. A. Saarela: Ultimately constant abelian complexity of infinite words. Journal of Automata, Languages and Combinatorics 14(3-4):255-258, 2009.
  26. Juha Honkala. Number systems and the injectivity problem for matrix representations of free monoids. International Journal of Algebra and Computation 19 (2009) 229-233.
  27. Juha Honkala. The equality problem for infinite words generated by primitive morphisms. Information and Computation 207 (2009) 900-907.
  28. Juha Honkala. On the simplification of infinite morphic words. Theor. Comput. Sci. 410 (2009) 997-1000.
  29. Stepan Holub and Kalle Saari. On highly palindromic words. Discrete Appl. Math. 157 (2009), no. 5, 953-959.
  30. James Currie and Kalle Saari. Least periods of factors of infinite words. Theor. Inform. Appl. 43 (2009), no. 1, 165-178.
  31. Svetlana Puzynina. On periodicity of generalized two-dimensional infinite words. Information and Computation 207:11 (2009) 1315-1328.
  32. Vesa Halava, Jarkko Kari and Yuri Matiyasevich. On Post Correspondence Problem for Letter Monotonic Languages. Theor. Comput. Sci. 410:30-32 (2009) 2957-2960.
  33. Juhani Karhumäki. On the power of cooperating morphisms via reachability problems. Internat. J. Found. Comput. Sci. 20 (2009) 803-818.
  34. Julien Cassaigne, Juhani Karhumäki and Petri Salmela. Conjugacy of finite biprefix codes. Theor. Comput. Sci. 410:24-25 (2009) 2345-2351.
  35. Vesa Halava, Tero Harju and Tomi Kärki. The theorem of Fine and Wilf for relational periods. RAIRO Inform. Théor. Appl. 40 (2009) 209-220.
  36. Vesa Halava, Tero Harju, Tomi Kärki and Patrice Séébold. Overlap-freeness in infinite partial words. Theoret. Comput. Sci. 410 (2009) 943-948.
  37. Michael Domaratzki and Alexander Okhotin. State complexity of power. Theoret. Comput. Sci. 410 (2009), no. 24-25, 2377-2392.
  38. Juha Honkala. Sparse and slender subsets of monoids. Semigroup Forum 76 (2008) 51-57.
  39. Juha Honkala. Cancellation and periodicity properties of iterated morphisms. Theoretical Computer Science 391 (2008) 61-64.
  40. Julien Cassaigne, Tomi Kärki and Luca Zamboni. Relationally periodic sequences and subword complexity. Developments in language theory, 196-205, Lecture Notes in Comput. Sci. 5257, Springer, Berlin, 2008.
  41. Tomi Kärki. Compatibility relations on codes and free monoids. Theor. Inform. Appl. 42 (2008), no. 3, 539-552.
  42. Svetlana Puzynina and S. V. Avgustinovich. On periodicity of two-dimensional words. Theoretical Computer Science 391 (2008) 178-187.
  43. Svetlana Puzynina. Perfect colorings of radius r>1 of the infinite rectangular grid. Siberian Electronic Mathematical Reports (2008) 283-292.
  44. Galina Jirásková and Alexander Okhotin. On the state complexity of operations on two-way finite automata. Developments in language theory, 443-454, Lecture Notes in Comput. Sci., 5257, Springer, Berlin, 2008.
  45. Alexander Okhotin. Homomorphisms preserving linear conjunctive languages. J. Autom. Lang. Comb. 13 (2008), no. 3-4, 299-305.
  46. Alexander Okhotin. Unambiguous Boolean grammars. Inform. and Comput. 206 (2008), no. 9-10, 1234-1247.
  47. Marie-Pierre Béal, Eugen Czeizler, Jarkko Kari and Dominique Perrin. Unambiguous Automata. Mathematics in Computer Science 1(4) (2008) 625-638.
  48. Juhani Karhumäki, Jarkko Kari and Joachim Kupke. Binary operations on automatic functions. RAIRO Inform. Théor. Appl. 42 (2008) 217-236.
  49. Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, and Igor Potapov. Matrix equations and Hilbert's tenth problem. Internat. J. Algebra and Computation 18 (2008) 1-11.
  50. Tero Harju and Dirk Nowotka. Bordered conjugates of words over large alphabets. Electronic J. Combin. 15(1) N41 (2008) 7 pages (electronic).
  51. Vesa Halava, Tero Harju and Tomi Kärki. Square free partial words. Inform. Process. Lett. 108 (2008) 290-292.
  52. Vesa Halava, Tero Harju, Mika Hirvensalo and Juhani Karhumäki. Post Correspondence Problem for short words. Inform. Process. Lett. 108 (2008) 115-118.
  53. Vesa Halava, Tero Harju and Tomi Kärki. Interaction properties of relational words. Discrete Math. Theoret. Comput. Sci. 10 (2008) 87-112.
  54. Tero Harju, Chang Li and Ion Petre. Parallel complexity of signed graphs for gene assembly in ciliates. Soft Computing 12 (2008) 731-737.
  55. Jean-Pierre Duval, Tero Harju and Dirk Nowotka. Unbordered Factors and Lyndon Words. Discrete Math. 308 (2008) 2261-2264.
  56. Vesa Halava, Tero Harju and Tomi Kärki. Defect theorems with compatibility relations. Semigroup Forum 76 (2008) 1-24.
  57. Elena Czeizler, Štěpán Holub, Juhani Karhumäki, and Markku Laine. Intricacies of simple word equations: an example. Internat. J. Found. Comput. Sci. 18(6), 1167-1175, 2007.
  58. Juha Honkala. A periodicity property of iterated morphisms. Theor. Inform. Appl. 41(2), 215-223, 2007.
  59. Juha Honkala. The D0L ω-equivalence problem. Internat. J. Found. Comput. Sci. 18(1), 181-194, 2007.
  60. Juha Honkala. A new bound for the D0L sequence equivalence problem. Acta Inform. 43(6), 419-429, 2007.
  61. Elena Czeizler, Juhani Karhumäki. On non-periodic solutions of independent systems of word equations over three unknowns. Internat. J. Found. Comput. Sci. 18(4), 873--897, 2007.
  62. Eugene Czeizler and Jarkko Kari. A tight linear bound on the synchronization delay of bijective automata. Theor. Comput. Sci. 380(1-2): 23-36, 2007
  63. Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg. Finite metrics in switching classes. Discrete Appl. Math., 155 (2007), 68-73.
  64. Vesa Halava, Tero Harju, and Juhani Karhumäki. Structure of infinite solutions of marked and binary Post Correspondence problems. Theory of Comp. Syst. 40 (2007), 43-54.
  65. Vesa Halava, Tero Harju, Juhani Karhumäki, and Michel Latteux. Extensions of the decidability of the marked PCP to instances with unique blocks. Theoret. Comput. Sci. 380 (2007), 355-362.
  66. Tero Harju, and Dirk Nowotka. Periodicity and unbordered words: a proof of the extended Duval conjecture. J. Assoc. Comput. Mach. 54(4) (July 2007).
  67. Vesa Halava, Tero Harju and Mika Hirvensalo: Undecidability Bounds for Integer Matrices using Claus Instances. Internat. J. Found. Comput. Sci. 18 (2007), 931-948.
  68. Vesa Halava, Tero Harju and Tomi Kärki: Codes of relational words. Theoret. Comput. Sci. 389 (2007), 237-249.
  69. Vesa Halava and Tero Harju: On Markov's Undecidability Theorem for Integer Matrices. Semigroup Forum 75 (2007), 173-80.
  70. Jurriaan Hage and Tero Harju: Towards a characterization of bipartite switching classes by means of forbidden subgraphs. Discussiones Mathematicae Graph Theory 23 (2007) 471-483.
  71. Gheorghe Paun, Mario de J. Perez-Jimenez, and Arto Salomaa. Spiking Neural P Systems: An Early Survey. Internat. J. Found. Comput. Sci., 18(3):435-455, 2007.
  72. Arto Salomaa, Kai Salomaa, and Sheng Yu. State complexity of combined operations. Theoret. Comput. Sci., 383(2-3):140-152, 2007.
  73. Arto Salomaa. Subword Balance in Binary Words, Languages and Sequences. Fund. Inform. , 75(1-4):469-482, 2007.
  74. Yo-Sub Han, Arto Salomaa, Kai Salomaa, Derick Wood and Sheng Yu. On the Existence of Prime Decompositions. Theor. Comput. Sci. , 376(1-2):60-69, 2007.
  75. Vesa Halava and Mika Hirvensalo. Improved Matrix Pair Undecidability Results. Acta Inform. 44: 191-205, 2007.
  76. Francesco Pappalardi, Arto Lepistö, and Kalle Saari. Transposition Invariant Words. Theor. Comput. Sci. 380(3): 377-387, 2007.
  77. Juha Honkala. The ultimate equivalence problem for uniform HDT0L systems. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS No. 90, 127-130, 2006.
  78. Juha Honkala. On the problem whether the image of an N-rational series equals N. Fund. Inform. 73(1-2), 127-132, 2006.
  79. Juha Honkala. The base problem for D0L Parikh sets. Internat. J. Found. Comput. Sci. 17(2), 465-473, 2006.
  80. Manfred Droste, Jarkko Kari, and Paula Steinby. Observations on the Smoothness Properties of Real Functions Computed by Weighted Finite Automata. Fundam. Inform.,73(1-2): 99-106, 2006.
  81. Cunsheng Ding and Arto Salomaa. On Some Problems of Mateescu Concerning Subword Occurrences. Fund. Inform. , 73(1-2):65-79, 2006.
  82. Cunsheng Ding and Arto Salomaa. Secret Sharing Schemes with Nice Access Structures. Fund. Inform. , 73(1-2):51-63, 2006.
  83. Arto Salomaa and Sheng Yu. Subword Conditions and Subword Histories. Information and Computation , 204(12):1741-1755, 2006.
  84. Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg. Embedding linear orders in grids. Acta Informatica 42 (2006), 419-428.
  85. Tero Harju and Dirk Nowotka. On unique factorizations of primitive words. Theoret. Comput. Sci. (2006) 356, 186-189.
  86. Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, and Grzegorz Rozenberg: The embedding problem for switching classes of graphs. Fundamenta Inf. 74 (2006), 1-17.
  87. Tero Harju and Dirk Nowotka: Periods in extensions of words. Acta Inf. 43 (2006), 165-171.
  88. Vesa Halava, Tero Harju, and Juhani Karhumäki. Undecidability in omega-regular languages. Fundamenta Inf. 72, 119-125, 2006.
  89. Vesa Halava, Tero Harju, and Mika Hirvensalo. Positivity of second order linear recurrent sequences. Discrete Applied Math.,154, 447-451, 2006.
  90. Vesa Halava and Tero Harju. Undecidability of Infinite Post Correspondence Problem for Instances of Size 9. Theory Inform. Appl., 40(4), 551-558, 2006.
  91. Juhani Karhumäki, Michal Kunc, and Alexander Okhotin. Computing by commuting. Theoret. Comput. Sci., 356(1-2):201-211, 2006.
  92. Alexander Okhotin. Computational universality in one-variable language equations. Fund. Inform., 2006.
  93. Alexander Okhotin. Generalized lr parsing algorithm for boolean grammars. Internat. J. Found. Comput. Sci., 2006.
  94. Vincent Bernardi, Bruno Durand, Enrico Formenti, and Jarkko Kari. A new dimension sensitive property for cellular automata. Theoret. Comput. Sci., 345(2-3):235-247, 2005.
  95. Christian Choffrut and Juhani Karhumäki. Some decision problems on integer matrices. Theor. Inform. Appl., 39(1):125-131, 2005.
  96. Elena Czeizler. The non-parametrizability of the word equation xyz=zvx: a short proof. Theoret. Comput. Sci., 345(2-3):296-303, 2005.
  97. Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, and Michel Latteux. Equality sets for recursively enumerable languages. Theor. Inform. Appl., 39(4):661-675, 2005.
  98. Vesa Halava, Tero Harju, and Michel Latteux. Representation of regular languages by equality sets. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (86):224-228, 2005.
  99. Vesa Halava, Tero Harju, and Michel Latteux. Equality sets of prefix morphisms and regular star languages. Inform. Process. Lett., 94(4):151-154, 2005.
  100. Tero Harju, Arto Lepistö, and Dirk Nowotka. A characterization of periodicity of bi-infinite words. Theoret. Comput. Sci., 347(1-2):419-422, 2005.
  101. Tero Harju and Dirk Nowotka. Counting bordered and primitive words with a fixed weight. Theoret. Comput. Sci., 340(2):273-279, 2005.
  102. Tero Harju and Dirk Nowotka. On the equation xk=z1k1z2k2 ···znkn in a free semigroup. Theoret. Comput. Sci., 330(1):117-121, 2005.
  103. Juha Honkala. An n 2-bound for the ultimate equivalence problem of certain D0L systems over an n-letter alphabet. J. Comput. System Sci., 71(4):506-519, 2005.
  104. Juha Honkala. The equivalence problem for languages defined by transductions on D0L languages. Int. J. Comput. Math., 82(8):911-918, 2005.
  105. Juha Honkala. The class of HDT0L sequences is closed with respect to rational functions. Inform. Process. Lett., 94(4):155-158, 2005.
  106. Juha Honkala. The language equivalence problem for HD0L systems having D0L growths. Theoret. Comput. Sci., 330(1):123-133, 2005.
  107. Juhani Karhumäki, Michel Latteux, and Ion Petre. Commutation with codes. Theoret. Comput. Sci., 340(2):322-333, 2005.
  108. Juhani Karhumäki, Michel Latteux, and Ion Petre. Commutation with ternary sets of words. Theory Comput. Syst., 38(2):161-169, 2005.
  109. Juhani Karhumäki, Wojciech Plandowski, and Wojciech Rytter. On the complexity of decidable cases of the commutation problem of languages. Theoret. Comput. Sci., 337(1-3):105-118, 2005.
  110. Jarkko Kari. Theory of cellular automata: a survey. Theoret. Comput. Sci., 334(1-3):3-33, 2005.
  111. Alexander Okhotin. The dual of concatenation. Theoret. Comput. Sci., 345(2-3):425-447, 2005.
  112. Alexander Okhotin. A characterization of the arithmetical hierarchy by language equations. Internat. J. Found. Comput. Sci., 16(5):985-998, 2005.
  113. Alexander Okhotin. Unresolved systems of language equations: expressive power and decision problems. Theoret. Comput. Sci., 349(3):283-308, 2005.
  114. Alexander Okhotin and Kai Salomaa. Contextual grammars with uniform sets of trajectories. Fund. Inform., 64(1-4):341-351, 2005.
  115. Tatjana Petković and Saeed Salehi. Positive varieties of tree languages. Theoret. Comput. Sci., 347(1-2):1-35, 2005.
  116. Saeed Salehi. Polynomially bounded recursive realizability. Notre Dame J. Formal Logic, 46(4):407-417 (electronic), 2005.
  117. Saeed Salehi. Varieties of tree languages definable by syntactic monoids. Acta Cybernet., 17(1):21-41, 2005.
  118. J. Berstel, J. Karhumäki, and D. Perrin. Preface: Special issue on combinatorics on words. Internat. J. Found. Comput. Sci., 15(2):223-224, 2004.
  119. Eugen Czeizler. On the size of the inverse neighborhoods for one-dimensional reversible cellular automata. Theoret. Comput. Sci., 325(2):273-284, 2004.
  120. Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg. Zebra factorizations in free semigroups. Semigroup Forum, 68(3):365-372, 2004.
  121. Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg. Transitivity of local complementation and switching on graphs. Discrete Math., 278(1-3):45-60, 2004.
  122. Jurriaan Hage and Tero Harju. A characterization of acyclic switching classes of graphs using forbidden subgraphs. SIAM J. Discrete Math., 18(1):159-176 (electronic), 2004.
  123. Vesa Halava and Tero Harju. Undecidability in matrices over Laurent polynomials. Adv. in Appl. Math., 33(4):747-752, 2004.
  124. Tero Harju and Juhani Karhumäki. Many aspects of defect theorems. Theoret. Comput. Sci., 324(1):35-54, 2004.
  125. Tero Harju and Dirk Nowotka. Border correlation of binary words. J. Combin. Theory Ser. A, 108(2):331-341, 2004.
  126. Tero Harju and Dirk Nowotka. Minimal Duval extensions. Internat. J. Found. Comput. Sci., 15(2):349-354, 2004.
  127. Tero Harju and Dirk Nowotka. The equation x i=y jz k in a free semigroup. Semigroup Forum, 68(3):488-490, 2004.
  128. Juha Honkala. It is decidable whether the image of an N-rational sequence has a base. J. Number Theory, 108(2):209-216, 2004.
  129. Juha Honkala. Bounds for the D0L language equivalence problem. Inform. and Comput., 190(1):70-80, 2004.
  130. Juha Honkala. On infinite HD0L words having sparse letters. Int. J. Comput. Math., 81(2):133-139, 2004.
  131. Juha Honkala and Michel Rigo. Decidability questions related to abstract numeration systems. Discrete Math., 285(1-3):329-333, 2004.
  132. Juhani Karhumäki and Jeffrey Shallit. Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A, 105(2):335-347, 2004.
  133. Mohammad Ardeshir, Wim Ruitenburg, and Saeed Salehi. Intuitionistic axiomatizations for bounded extension Kripke models. Ann. Pure Appl. Logic, 124(1-3):267-285, 2003.
  134. J. Berstel and J. Karhumäki. Combinatorics on words-a tutorial. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (79):178-228, 2003.
  135. S. Bogdanović, M. Cirić, B. Imreh, T. Petković, and M. Steinby. On local properties of unary algebras. Algebra Colloq., 10(4):461-478, 2003.
  136. Jurriaan Hage, Tero Harju, and Emo Welzl. Euler graphs, triangle-free graphs and bipartite graphs in switching classes. Fund. Inform., 58(1):23-37, 2003. First International Conference on Graph Transformation (ICGT 2002).
  137. Vesa Halava, Tero Harju, and Juhani Karhumäki. Decidability of the binary infinite Post correspondence problem. Discrete Appl. Math., 130(3):521-526, 2003.
  138. Tero Harju and Dirk Nowotka. On the independence of equations in three variables. Theoret. Comput. Sci., 307(1):139-172, 2003. Words.
  139. Tero Harju and Dirk Nowotka. Periodicity and unbordered segments of words. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (80):162-167, 2003.
  140. Mika Hirvensalo and Sebastian Seibert. Lower bounds for Las Vegas automata by information theory. Theor. Inform. Appl., 37(1):39-49, 2003.
  141. Juha Honkala. A bound for the ω-equivalence problem of polynomial D0L systems. Theor. Inform. Appl., 37(2):149-157, 2003.
  142. Juha Honkala. The DF0L language equivalence problem. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (80):143-152, 2003.
  143. Juha Honkala. On D0L systems with finite axiom sets. Acta Cybernet., 16(1):29-35, 2003.
  144. Juha Honkala. Decidability results for Watson-Crick D0L systems with nonregular triggers. Theoret. Comput. Sci., 302(1-3):481-488, 2003.
  145. Juha Honkala. The equivalence problem of polynomially bounded D0L systems-a bound depending only on the size of the alphabet. Theory Comput. Syst., 36(1):89-103, 2003.
  146. Juha Honkala. On images of D0L and DT0L power series. Theoret. Comput. Sci., 290(3):1869-1882, 2003.
  147. Juha Honkala and Keijo Ruohonen. On the images of N-rational sequences counting multiplicities. Internat. J. Algebra Comput., 13(3):303-321, 2003.
  148. J. Karhumäki and L. P. Lisovik. A simple undecidable problem: the inclusion problem for finite substitutions on ab *c. Inform. and Comput., 187(1):40-48, 2003.
  149. J. Karhumäki and L. P. Lisovik. The equivalence problem of finite substitutions on ab *c, with applications. Internat. J. Found. Comput. Sci., 14(4):699-710, 2003.
  150. Juhani Karhumäki, Ján Manuch, and Wojciech Plandowski. A defect theorem for bi-infinite words. Theoret. Comput. Sci., 292(1):237-243, 2003. Selected papers in honor of Jean Berstel.
  151. Juhani Karhumäki, Wojciech Plandowski, and Wojciech Rytter. The complexity of compressing subsegments of images described by finite automata. Discrete Appl. Math., 125(2-3):235-254, 2003.
  152. Jarkko Kari. Synchronizing finite automata on Eulerian digraphs. Theoret. Comput. Sci., 295(1-3):223-232, 2003. Mathematical foundations of computer science (Mariánské Lázne, 2001).
  153. Elena Petre. Watson-Crick ω-automata. J. Autom. Lang. Comb., 8(1):59-70, 2003.
  154. Saeed Salehi. Provably total functions of basic arithmetic. MLQ Math. Log. Q., 49(3):316-322, 2003.
  155. Pavol Duriš and Ján Manuch. On the computational complexity of infinite words. Theoret. Comput. Sci., 295(1-3):141-151, 2003. Mathematical foundations of computer science (Mariánské Lázne, 2001).
  156. Christian Choffrut, Juhani Karhumäki, and Nicolas Ollinger. The commutation of finite sets: a challenging problem. Theoret. Comput. Sci., 273(1-2):69-79, 2002. WORDS (Rouen, 1999).
  157. Karel Culik, II, Juhani Karhumäki, and Jarkko Kari. A note on synchronized automata and road coloring problem. Internat. J. Found. Comput. Sci., 13(3):459-471, 2002.
  158. Vesa Halava, Tero Harju, and Mika Hirvensalo. Binary (generalized) Post correspondence problem. Theoret. Comput. Sci., 276(1-2):183-204, 2002.
  159. Tero Harju, Oscar Ibarra, Juhani Karhumäki, and Arto Salomaa. Some decision problems concerning semilinearity and commutation. J. Comput. System Sci., 65(2):278-294, 2002.
  160. Tero Harju and Dirk Nowotka. Density of critical factorizations. Theor. Inform. Appl., 36(3):315-327, 2002.
  161. Mika Hirvensalo. Universality and quantum computing. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (78):199-203, 2002.
  162. Mika Hirvensalo. Computing with quanta-impacts of quantum theory on computation. Theoret. Comput. Sci., 287(1):267-298, 2002. Natural computing.
  163. Juha Honkala. On the simplification of HD0L power series. J.UCS, 8(12):1040-1046 (electronic), 2002.
  164. Juha Honkala. A new class of algebraic series having a decidable equivalence problem. Fund. Inform., 53(3-4):315-320, 2002.
  165. Juha Honkala. A note on systems of alternative word equations. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (78):237-240, 2002.
  166. Juha Honkala. Remarks concerning the D0L ω-equivalence problem. Internat. J. Found. Comput. Sci., 13(5):769-777, 2002.
  167. Juha Honkala. The equivalence problem for DF0L languages and power series. J. Comput. System Sci., 65(2):377-392, 2002.
  168. Juha Honkala. The equality problem for Parikh simple algebraic power series. Inform. Process. Lett., 84(2):57-60, 2002.
  169. Juha Honkala. On infinite words generated by polynomial D0L systems. Discrete Appl. Math., 116(3):297-305, 2002.
  170. Juraj Hromkovic, Sebastian Seibert, Juhani Karhumäki, Hartmut Klauck, and Georg Schnitger. Communication complexity method for measuring nondeterminism in finite automata. Inform. and Comput., 172(2):202-217, 2002.
  171. J. Karhumäki, A. Lepistö, and W. Plandowski. Locally periodic versus globally periodic infinite words. J. Combin. Theory Ser. A, 100(2):250-264, 2002.
  172. Juhani Karhumäki and Ján Manuch. Multiple factorizations of words and defect effect. Theoret. Comput. Sci., 273(1-2):81-97, 2002. WORDS (Rouen, 1999).
  173. Juhani Karhumäki and Ion Petre. Conway's problem for three-word sets. Theoret. Comput. Sci., 289(1):705-725, 2002.
  174. Jarkko Kari. Synchronization and stability of finite automata. J.UCS, 8(2):270-277 (electronic), 2002. Advances and trends in automata and formal languages.
  175. Saeed Salehi. Decidable formulas of intuitionistic primitive recursive arithmetic. Rep. Math. Logic, (36):55-61, 2002.
  176. Julien Cassaigne, Juhani Karhumäki, and Ján Manuch. On conjugacy of languages. Theor. Inform. Appl., 35(6):535-550 (2002), 2001. A tribute to Aldo de Luca.
Last modified: