Lucian Ilie:  Publications (some reprints available here)

  Chapters in Books

  1. L. Ilie, Regular Expression Matching, in: Ming-Yang Kao, ed., Encyclopedia of Algorithms , SpringerScience+BuisinessMedia, New York, 2008, 768 -- 771.

  Refereed journals

  1. M. Crochemore, L. Ilie, and L. Tinta, The "runs" conjecture, Theoret. Comput. Sci. (special issue for selected papers from WORDS'09), to appear.
  2. L. Ilie and S. Ilie, Fast computation of neighbor seeds, Bioinformatics 25 (6) (2009) 822 -- 823.
  3. M. Crochemore, L. Ilie, and W. Rytter, Repetitions in strings: algorithms and combinatorics, Theoret. Comput. Sci. 410 (50) (2009) 5227 -- 5235.
  4. M. Crochemore and L. Ilie, Computing Longest Previous Factor in linear time and applications, Inform. Process. Lett. 106 (2008) 75 -- 80.
  5. M. Crochemore and L. Ilie, Maximal repetitions in strings, J. Comput. Syst. Sci. 74 (2008) 796 –- 807.
  6. L. Ilie and S. Ilie, Multiple spaced seeds for homology search, Bioinformatics 23 (22) (2007) 2969 -- 2977.
  7. S. Constantinescu and L. Ilie, The Lempel--Ziv complexity of fixed points of morphisms, SIAM J. Discrete Math. 21 (2) (2007) 466 -- 481.
  8. M. Crochemore, L. Ilie, and Emine Seid-Hilmi, The structure of factor oracles, Internat. J. Found. Comput. Sci. 18 (4) (2007) 781 -- 797.
  9. L. Ilie, A note on the number of squares in a word, Theoret. Comput. Sci. 380 (3) (2007) 373 -- 376.
  10. S. Constantinescu and L. Ilie, Fine and Wilf's theorem for abelian periods, Bulletin of EATCS 89 (2006) 167 -- 170.
  11. L. Ilie and C. Popescu, Viral genome compression and shortest common superstring problem, Fund. Inform. 73 (1-2) (2006) 153 -- 164.
  12. L. Ilie, S. Marcus, and I. Petre, Periodic and Sturmian languages,  Inform. Proc. Lett. 98 (6) (2006) 242 -- 246.
  13. L. Ilie, A simple proof that a word of length n has at most 2n distinct squares, J. Combin. Theory, Ser. A, 112 (1) (2005) 163 -- 164.
  14. M. Davidson and L. Ilie, Fast data compression with antidictionaries, Fund. Inform. 64 (1) (2005) 1 -- 16.
  15. L. Ilie, P. Ochem, and J. Shallit, A generalization of repetition threshold, Theoret. Comput. Sci. 345 (2-3) (2005) 359 -- 369.
  16. S. Constantinescu and L. Ilie, Generalized Fine and Wilf'stheorem forarbitrary number of periods, Theoret. Comput. Sci . 339 (1) (2005) 49 -- 60.
  17. L. Ilie and S. Yu, Follow automata, Inform.and Comput. 186(1) (2003), 1 -- 162.
  18. L. Ilie and S. Yu, Reducing NFAs by invariant equivalences, Theoret. Comput. Sci. 306, no. 1-3, (2003) 373 -- 390.
  19. L. Ilie, S. Yu, and K. Zhang, Word complexity and repetitions in words, Internat. J. Found. Comput. Sci. 15(1) (2004) 41 -- 55.
  20. V. Halava, T. Harju, and L. Ilie, Periods and binary words,  J. Combin. Theory, Ser. A, 89 (2000) 298 - 308.
  21. L. Ilie and W. Plandowski, Two-variable word equations, Theoret. Inform. Appl. (RAIRO) 34 (2000) 467 -- 501.
  22. L. Ilie, On lengths of words in context-free languages,  Theoret. Comput. Sci. 242 (2000) 327 - 359.
  23. L. Ilie, Gh. Paun, G. Rozenberg, and A. Salomaa, On strongly context-free languages, Discrete Appl. Math. 103 (2000) 158 - 165.
  24. L. Ilie and A. Salomaa, On the expressiveness of subset-sum representations, Acta Inform. 36 (2000) 665 - 672.
  25. L. Ilie, G. Rozenberg, and A. Salomaa, Acharacterization of poly-slender context-free languages, Theoret Inform. Appl. (RAIRO) 34 (2000) 77 - 86.
  26. L. Ilie, Subwords and power-free words are not expressible byword equations, Fund. Inform. 38 (1999) 109 - 118.
  27. L. Ilie and Arto Salomaa, 2-Testability and relabelings produce everything, J. Comput. System Sci. 56 (1998) 253 - 262.
  28. Tero Harju and L. Ilie, On quasi orders of words and the confluence property, Theoret. Comput. Sci. 200 (1998) 205 - 224.
  29. L. Ilie and Arto Salomaa, On well quasi orders of free monoids, Theoret. Comput. Sci. 204 (1998) 131 - 152.
  30. L. Ilie, Generalized factors of words, Fund. Inform. 33 (1998) 239 - 247.
  31. T. Harju and L. Ilie, Languages obtained from infinite words, RAIRO, Inform. Theor. Appl. 31 (1997) 445 -- 455.
  32. L. Ilie, On computational complexity of contextual languages, Theoret. Comput. Sci. 183 (1997) 33 - 44.
  33. V. Halava, T. Harju, and L. Ilie, On a geometric problem of zig-zags, Inform. Process. Lett. 62 (1997) 1 - 4.
  34. L. Ilie, On the computational complexity of Marcus contextual languages, Fund. Inform. 30 (1997) 161 - 167.
  35. L. Ilie, Collapsing hierarchies in parallel communicating grammar systems with communication by command, Comput. Artificial Intelligence 1 5(1996) 173 - 184.
  36. L. Ilie,V. Mitrana, Binary self-adding sequences and languages, Int. J. Comput Math. 62 (1996) 171-181.
  37. L. Ilie, On subwords of infinite words, Discrete Appl. Math. 63(1995), 277 - 279.
  38. L. Ilie, On a conjecture about slender context-free languages, Theoret. Comput. Sci. 132 (1994) 427 - 434.
  Refereed conference proceedings
  1. M. Crochemore, L. Ilie, and L. Tinta, The "runs" conjecture, Proc. of the 7th International Conference on Combinatorics on Words (WORDS'09) (Salerno, 2009), to appear.
  2. L. Ilie and L. Tinta, Fast Algorithms for Longest Common Extension, Proc. of the 16th International Symposium on String Processing and Information Retrieval (SPIRE'09), Lecture Notes in Comput. Sci. 5721, Springer, Heidelberg, 2009, 302 -- 309.
  3. L. Ilie and S. Ilie, Efficient computation of good neighbor seeds, 17th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB'09) & 8th European Conference for Computational Biology (ECCB'09) , Stockholm, 2009.
  4. M. Crochemore, L. Ilie, C. Iliopoulos, M. Kubica, W. Rytter, and T. Walen, LPF computation revisited, Proc. of the 20th International Workshop on Combinatorial Algorithms (IWOCA'09) , (Czech Republic), Lecture Notes in Comput.~Sci. 5874 Springer, Heidelberg, 2009, 158--169.
  5. L. Ilie and S. Ilie, Improved algorithms for local alignment, 16th Annual International Conference Intelligent Systems for Molecular Biology (ISMB'08) , Toronto, 2008.
  6. M. Crochemore, L. Ilie, and L. Tinta, Towards a solution to the "runs" conjecture, in: P. Ferragina and G. Landau (Eds.), Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (CPM'08) (Pisa, Italy), Lecture Notes in Comput. Sci. 5029 , Springer, Berlin, 2008, 290 –- 302.
  7. M. Crochemore and L. Ilie, Understanding maximal repetitions in strings, in: S. Albers and P. Weil, eds., Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science (STACS'08) (Bordeaux, 2008), http://drops.dagstuhl.de/opus/volltexte/2008/1344.
  8. M. Crochemore, L. Ilie, and W.F. Smyth, A simple algorithm for computing the Lempel--Ziv factorization, Proc. of 17th Data Compression Conference (DCC'08) (Snowbird, Utah, USA), to appear.
  9. L. Ilie and S. Ilie, Fast computation of multiple spaced seeds for homology search, in: R. Giancarlo, S. Hannenhalli, eds.,  Proc. of the 7th Workshop on Algorithms in Bioinformatics (WABI'07) (Philadelphia, 2007), Lecture Notes in Bioinformatics 4645 , Springer, Berlin, 2007, 346–358.
  10. L. Ilie and S. Ilie, Long spaced seeds for homology search, in: H. Arabnia, M.Q. Yang, and J.Y. Yang, eds., Proc. of the 2007 International Conference on Bioinformatics and Computational Biology (BIOCOMP'07) (Las Vegas, 2007), Vol. I, CSREA Press, Las Vegas, 2007, 3 -- 8.
  11. M. Crochemore and L. Ilie, Analysis of maximal repetitions in strings, in: L. Kucera, A. Kucera, eds., Proc. of  the 32nd Mathematical Foundations of Computer Science (MFCS'07) (Cesky Krumlov, Czech Republic, 2007), Lecture Notes in Comput. Sci. 4708 , 2007, 465--476.
  12. M. Crochemore, L. Ilie, and E. Seid-Hilmi, Factor Oracles, Proc. of the 11th International Conference on Implementation and Application of Automata (CIAA'06) (Taipei, Taiwan, 2006),   Lecture Notes in Comput. Sci. 4094 , Springer, Berlin, Heidelberg, 2006, 78 -- 89.
  13. S. Constantinescu and L. Ilie, The Lempel--Ziv complexity of fixed points of morphisms, Proc. of  the 31st Mathematical Foundations of Computer Science (MFCS'06) , Lecture Notes in Comput. Sci. 4162 , Springer, Berlin, 2006, 280 -- 291.
  14. L. Ilie, L. Tinta, C. Popescu, and K. Hill, Viral genome compression, in: C. Mao, T. Yokomori, eds., Proc. of the 12th International Meeting on DNA Computing (DNA'06) (Seoul, Korea, 2006), Lecture Notes in Comput. Sci. 4287 , Springer, Berlin, 2006, 111 -- 126.
  15. L. Ilie and R. Solis-Oba, Strategies for DNA self-assembly in ciliates, in: C. Mao, T. Yokomori, eds.,  Proc. of the 12th International Meeting on DNA Computing (DNA'06) (Seoul, Korea, 2006), Lecture Notes in Comput. Sci. 4287 , Springer, Berlin, 2006, 71 -- 82.
  16. S. Constantinescu and L. Ilie, The Lempel-Ziv complexity of fixed points of morphisms, SIAM Conference on Discrete Mathematics , Victoria, 2006.
  17. L. Ilie, A note on the number of distinct squares in aword, in: S. Brlek, C. Reutenauer, eds., Proc. of the 5th International Conference on Combinatorics on Words (WORDS'05 ) (Montreal, 2005), LaCIM 36 , Montreal, 2005, 289 -- 294.  
  18. L. Ilie, R. Solis-Oba, and S. Yu, Reducing NFAs by equivalences and preorders, in: A. Apostolico, M. Crochemore, K. Park, eds., Proc. of 16th Annual Symposium on Combinatorial Pattern Matching (CPM'05) (Jeju island, Korea, 2005), Lecture Notes in Comput. Sci. 3537, Springer, Berlin, 2005, 310 -- 321.
  19. L. Ilie, P. Ochem and J. Shallit, A generalization of repetition threshold, in: J. Fiala, V. Koubek, J. Kratochvil, eds., Proc. of 29th International Symposium on Mathematical Foundations of Computer Science (MFCS'04) (Prague, 2004), Lecture Notes in Comput. Sci. 3153 , Springer, Berlin, 2004, 818 -- 826.
  20. S. Constantinescu and L. Ilie, Fine and Wilf'stheorem for any number of periods, in: T. Harju, J. Karhumaki, eds., Proc. of the 4th International Conference on Combinatorics on Words (WORDS'03) , (Turku, 2003), TUCS General Publication, 27 (2003) 65 -- 74.
  21. L. Ilie, B. Shan and S. Yu ,Fast algorithms for extended regular expression matching and searching, in: H. Alt and M. Habib, eds., Proc ofthe 20th Symposium on Theoretical Aspects of Computer Science (STACS'03) (Berlin, 2003), Lecture Notesin Comput. Sci. 2607 , Springer, Berlin, 2003, 179 -- 190.
  22. L. Ilie and S. Yu ,Algorithms for computing small NFAs, in:  K. Diks, W. Rytter, eds., Proc.of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS'02) (Warszawa,2002),Lecture Notes in Comput. Sci. 2420 , Springer, Berlin, 2002, 328 -- 340.
  23. L. Ilie and S. Yu ,Constructing NFAs by optimal use of positions in regular expressions,  in: A.Apostolico, M. Takeda, eds., Proc. of the 13th Annual Symposium on Combinatorial Pattern Matching (CPM'02) (Fukuoka, 2002), Lecture Notes in Comput. Sci. 2373 , Springer, Berlin, 2002, 279 -- 288.
  24. L. Ilie, S. Yu, and K. Zhang, Repetition complexity of words, in: O. Ibarra, L. Zhang, eds., Proc.of the 8th Annual International Computing and Combinatorics Conference (COCOON'02) (Singapore, 2002),Lecture Notes in Comput. Sci. 2387 ,Springer, Berlin, 2002, 320 -- 329.
  25. L. Ilie and W. Plandowski, Two-variable word equations, in: H. Reichel, S. Tison, eds., Proc. ofthe 17th Symposium on Theoretical Aspects of Computer Science (STACS'00) (Lille, 2000), Lecture Notes in Comput. Sci. 1770 , Springer-Verlag, Berlin, 2000, 122 - 132.
  26. L. Ilie, An attempt to define a class of mildly context-sensitive languages, in: A. Adam, P. Domosi, eds., Proc. of the 8th International Conference on Automata and Formal Languages (ICAFL'96) (Salgotarjan, 1996), Publ. Math. Debrecen 54 (1999) 865 - 876.
  27. L. Ilie, Remarks on well quasi orders of words, in: S.Bozapalidis, ed.,  Proc. of the 3rd Developments in Language Theory Conference (DLT'97)   (Thessaloniki,1997), Aristotle Univ. of Thessaloniki, 1998, 399 - 411.
  28. L. Ilie, On ambiguity in internal contextual languages, in: C. Martin-Vide, ed., Mathematical and computational analysis of natural language (Tarragona,1996), Benjamins, Amsterdam, 1998, 29 - 45.
  29. L. Ilie, On disjunctivity, ultimate periodicity, and ultimate identity of Paun-Salomaa self-reading sequences, in: J. Dassow, G. Rozenberg, A. Salomaa, eds., Proc. of the 2nd Developments in Language Theory Conference (DLT'95)  (Magdeburg 1995), World Sci.Publishing, River Edge, NJ, 1996, 44 - 53.
  30. L. Ilie and Arto Salomaa, On regular characterizations of languages using grammar systems, in: E. Csuhaj-Varju, ed., Grammar Systems: Recent results and perspectives (Budapest, 1996), Acta Cybernet. 12 (1996) 411 - 425.
  Invited papers and book chapters 
  1. L. Ilie, Combinatorial complexity measures for strings, Recent Advances in Formal Languages and Applications , Springer-Verlag, Berlin, Heidelberg, 2006, 149 -- 170.
  2. L. Ilie, G. Navarro, and S. Yu, On NFA reductions, in: J. Karhumaki et al., eds., Theory is Forever (Salomaa Festschrift), Lecture Notes in Comput. Sci. 3113 ,Springer-Verlag, Berlin, Heidelberg, 2004, 112 -- 124.
  3. L. Ilie and V. Mitrana, Crossing-over on languages: a formal representation of chromosomes recombination, in C. Martin-Vide, V.Mitrana, eds., Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back , Taylor and Francis, London, 2003, 391-401.
  4. L. Ilie, S. Yu, and K. Zhang, Repetition complexity of words, invited lecture, DCFS 2002 , (London, Canada, 2002).
  5. T. Harju and L. Ilie, Forbidden subsequences and permutations sortable on two parallel stacks, in: C. Martin-Vide, V. Mitrana, eds., Where Mathematics, Computer Science, Linguistics, and Biology Meet , Kluwer, Dordrecht, 2001, 267 -- 275.
  6. L. Ilie, On generalized slenderness of languages,in: M. Ito, Gh. Paun, S. Yu, eds., Words, Semigroups, and Transductions , World. Sci. Publ.,Singapore, 2001, 189 -- 202.
  7. L. Ilie, I. Petre, and G. Rozenberg, Uniformly scattered factors, in: C. Calude, Gh. Paun, eds., Finite Versus Infinite. Contributions to an Eternal Dilemma , Springer-Verlag, London, 2000, 187 - 198.
  8. L. Ilie, Some recent results on contextual languages, Bull. EATCS (The Formal Language Theory Column) 62 (1997) 176 -194.
  9. L. Ilie, The decidability of the generalized confluence problem for context-free languages, in, Gh. Paun, A. Salomaa, eds., NewTrends in Formal Languages. Control, Cooperation, and Combinatorics , Lecture Notes in Comput. Sci. 1218 ,Springer-Verlag, Berlin, Heidelberg, 1997, 454 - 464.
  10. L. Ilie, A. Ehrenfeucht, Gh. Paun, G. Rozenberg, and A. Salomaa,On the generative capacity of some classes of contextual grammars, Mathematical Linguistics and Related Topics, 1995, 105 - 118.
  11. L. Ilie, On contextual grammars with parallel derivation, in: Gh.Paun, ed., Mathematical Aspects of Natural and Formal Languages , World Sci. Publishing, Singapore, 1994, 165 - 172.
Back to home page