Information society uses results of pattern matching every day and its importance keeps rising. The pattern matching is no longer limited to ordinary texts. Searching in more complex structures is required like searching in trees (XML data structures), in 2D images, or in compressed data. The proposed project aims not only to extend our research results in Stringology, but also apply our knowledge in quite new topic dealing with pattern matching in trees that we call Arborology. Our strong background in parsing seems to be very efficiently utilized in Arborology. In Stringology we would like to continue on topics like multidimensional pattern matching, searching for regularities in strings, generalized string matching, and parallel approaches to pattern matching. In Data Compression we developed algorithms for exact pattern matching in compressed data. We want to improve our results and expand to approximate pattern matching.

GA201/09/0807, 2009 - 2009

• Doc.Ing. Jan Holub, Ph.D.

• Balík Miroslav Ing. Ph.D., Team Member (České vysoké učení technické v Praze, Fakulta elektrotechnická)
• Holub Jan doc. Ing. Ph.D. (České vysoké učení technické v Praze, Fakulta elektrotechnická)
• Janoušek Jan doc. Ing. Ph.D., Team Member (České vysoké učení technické v Praze, Fakulta elektrotechnická)
• Melichar Bořivoj prof. Ing. DrSc., Team Member (České vysoké učení technické v Praze, Fakulta elektrotechnická)
• Šupol Jan Ing. Ph.D., Team Member (České vysoké učení technické v Praze, Fakulta elektrotechnická)
• Vagner Ladislav Ing. Ph.D., Team Member (České vysoké učení technické v Praze, Fakulta elektrotechnická)
• Voráček Michal Ing. Ph.D., Team Member (České vysoké učení technické v Praze, Fakulta elektrotechnická)
• Žďárek Jan Ing. Ph.D., Team Member (České vysoké učení technické v Praze, Fakulta elektrotechnická)

• 2009: GUTH O., MELICHAR B.
  Searching All Seeds of Strings with Hamming Distance using Finite Automata (Paper in Conference Proceedings)
  In IMECS 2009: International MultiConference of Engineers and Computer Scientists. Hong Kong: The International Association of Engineers IAENG, 2009, p. 622-629. ISBN 978-988-17012-2-0.
  
• 2009: ĎURIAN B., HOLUB J., PELTOLA H., TARHIO J.
  Tuning BNDM with q-Grams (Paper in Conference Proceedings)
  In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments. Philadelphia: SIAM, 2009, p. 29-37. ISBN 978-0-89871-653-5.
  
• 2009: GUTH O., MELICHAR B.
  Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance (Paper)
  International Journal of Computer Science. 2009, vol. 36, no. 2, p. 137-146. ISSN 1819-656X.
  
• 2009: GUTH O.
  Searching Covers of Strings using Finite Automata ()
  [Doktorandské minimum]. Prague: CTU, Faculty of Electrical Engineering, Department of Computer Science and Engineering, 2009. 35 s.
  
• 2009: GUTH O.
  Searching Approximate Covers of Strings Using Finite Automata (Unpublished Lecture)
  [Nepublikovaná přednáška]. King's College London. 2009-02-06.
  
• 2009: FLOURI T., QAFMOLLA X.
  Linear Pattern Matching with Swaps for Short Patterns (Paper in Electronic Proceedings (CD-ROM or web))
  In Proceedings of the 10th International PhD Workshop on Systems and Control [CD-ROM]. Prague: Academy of Sciences of the Czech Republic, Institute of Information Theory and Automation, 2009, ISBN 978-80-903834-3-2.