Internship at formal languages theory research group / Internship

Person In Charge: Semyon Grigorev

We are looking for persons who are interested in formal languages theory and its application for static code analysis and graph database querying.

Algorithms for language intersection may be used in various areas such as graph databases, static code analysis, compressed data processing. For example, in terms of language-constrained path querying, a graph database may be considered as a finite automaton or a regular language. From this point of view, the result of path querying is an intersection of some regular language and the language specified by the query. The similar view on static code analysis is used in language reachability framework.

There are many problems in these areas and attempts to find solutions lead us to such fundamental problems in language theory as emptiness of language, closedness of language classes under intersection, etc. Our group works on theoretical and applied aspects of languages intersection and we propose the following possible areas of research:

  • Algorithm comparison, development, evaluation
    • Matrix-based algorithms for languages intersection
    • Parser combinators technique for graph querying
    • Deep comparison of classical parsing techniques in the context of graph querying
  • Areas of application exploration
    • Finding of new problems which may be formulated in terms of language intersection
    • Comparison of solutions, based on language intersection, with other approaches
  • Algorithms and their formalization in Coq.
  • Language classes and language specification formalisms comparison
    • A balance between expressivity and decidability of fundamental problems

Exact tasks will be formulated “by request”, but you can found examples of tasks on GitHub and choose preferable area of work. Feel free to request details in comments.

Requirements

  • Knowledge of fundamentals of formal languages theory
  • Math background: linear algebra, graph theory, logic

Would be useful

  • Functional programming skills (preferable F#, Scala)
  • Parallel programming and GPGPU programming skills