You have reached the online home of FLAReLab, the Formal Languages and Automata Research Lab. We are a part of the Department of Computer Science at St. Francis Xavier University in Antigonish, Nova Scotia, Canada.
In the same way that a flare illuminates the dark sky, research in theoretical computer science sheds light on the many unknowns scattered across the rest of computer science. Theoretical research forms the foundation of the study of computing, and although the interest in and value of “hot topics” ebbs and flows, theory is a constant presence lending perpetual insight to researchers and practitioners alike.
The members of FLAReLab study fundamental problems in formal language theory and automata theory together with select applications of these theoretical notions, intersecting with areas such as algorithm analysis, bioinformatics, coding theory, and software engineering. FLAReLab research has been presented at top international conferences and published in leading computer science journals, and its members have received a number of awards and accolades.
FLAReLab is led by Taylor J. Smith, an assistant professor and Alley Heaps Associate in the Department of Computer Science at St. Francis Xavier University.
Director of FLAReLab
Undergraduate Summer Research Student
(co-supervised with M. King)
Undergraduate Summer Research Student
St. Francis Xavier University
- November 14, 2023: Taylor J. Smith has been awarded a St. Francis Xavier University Research Council Grant valued at $7 000.
- July 29, 2023: Taylor J. Smith published a paper in the Journal of Automata, Languages, and Combinatorics with Kai Salomaa of Queen’s University.
- February 27, 2023: Alastair May is returning to the lab as an undergraduate summer research student, supported by an Alley Heaps Undergraduate Research Internship through St. Francis Xavier University.
- February 27, 2023: Liam Johnston is joining the lab as an undergraduate summer research student, supported by an Alley Heaps Undergraduate Research Internship through St. Francis Xavier University. He is co-supervised by Milton King.
- October 15, 2022: Alastair May travelled to Sackville, New Brunswick, Canada to present at the Science Atlantic MSCS 2022 conference, and won the Computer Science Communication Award for his talk.
- August 27, 2022: Taylor J. Smith travelled to Debrecen, Hungary to present at the NCMA 2022 conference.
- June 14, 2022: Alastair May received additional research support through the Canada Summer Jobs program.
- March 2, 2022: Alastair May is joining the lab as an undergraduate summer research student, supported by an Alley Heaps Undergraduate Research Internship through St. Francis Xavier University.
- September 2, 2021: Taylor J. Smith has been named an Alley Heaps Associate in the Department of Computer Science and will receive research support over the next three years valued at $15 000.
- August 1, 2021: Hello world! Taylor J. Smith started as an assistant professor at St. Francis Xavier University.
Please contact us directly with any media inquiries.
Two-Dimensional Formal Languages and Automata Theory
A major interest of FLAReLab lies in the study of formal languages and automata theory in two dimensions. Although going from strings to arrays may not seem like a big change, adding another dimension increases the computational power of a finite automaton drastically. FLAReLab members study fundamental properties of the two-dimensional automaton model together with applications to other areas of computer science, such as data storage and image recognition.
Visual Representations of Automata
Building on the Grail software package
, members of FLAReLab created a tool that takes Grail output and generates a visual representation of a finite automaton in LaTeX/TikZ code. The generated figure can then be added to research papers or educational materials, saving authors considerable time versus producing the figure manually. This work received the Computer Science Communication Award at the Science Atlantic MSCS 2022
Bio-Inspired Language Operations
Certain biological and genomic operations, such as insertion, deletion, splicing, and mutagenesis, can be modelled formally using language operations. In a collaboration with researchers from South Korea, members of FLAReLab studied these bio-inspired language operations and proved a number of decidability and algorithmic results that, taken together, establish the power of this modelling technique. Combining formal languages with bioinformatics may help future researchers uncover new findings without the need for a wet lab.
FLAReLab and its members graciously acknowledge funding support from the following sources:
If you are an undergraduate or graduate student who has an interest in formal languages, automata, or applications of theoretical computer science, feel free to get in touch! FLAReLab has openings for undergraduate summer research students, undergraduate honours thesis students, and graduate students applying to the Master of Science program.
Please read the information sheet for prospective students, and contact us if you have any questions about the application process or funding opportunities.