Grant: Discovery Grants Program - Individual

Introduction A (word) relation is a set of tuples such that each tuple consists of some fixed number n of words. Thus, we can talk about nD (n-dimensional) word relations. The two most well known kinds of word relations are 1D relations, which are known as (formal) languages and are sets of single words, and 2D relations, which are sets of pairs of words. An example of a 2D word relation is the set of word pairs (u,v) such that the edit distance d(u,v) is at most 2. Theoretical Computer Science provides (1) methods to represent a possibly infinite word relation as a finite object (2) algorithms that operate on these finite objects (3) methods to establish whether algorithmic questions on these objects are hard or even undecidable. Representations of Word Relations Depending on their representation method, we have various types of relations. For example, rational relations are relations representable by regular expressions, or by (finite) automata. Automata for 2D rational relations are called transducers. Regular expressions are convenient for human use; for example 1D regular expressions are ubiquitous in computer programming and are now used even by biologists. However, many algorithms for rational relations operate better on their corresponding automata representations. Some rational word relations are called synchronous; they can be represented by regular expressions of a certain simple format and have certain algorithms that operate faster than those of general rational relations. But there are word relations that are not rational. These are usually represented by automata with accessories like counters and stacks. Motivation, Objectives, Significance Rational relations have applications in various domains, such as reachability in string programs, graph databases, and independence conditions on formal languages. However, according to some authors, "while the theory of languages is very mature, our understanding of nD relations is still lagging behind", and some problems on word relations "seem out of reach in the current state of the theory". Motivated by these considerations, three objectives of the planned work are: (1) Investigate various concepts of synchronous nD relations, in particular for n>2, as well as various rational intersection problems; (2) Investigate algorithmic and decidability questions on word relations and, when possible, implement algorithms that can be applied to questions in biocomputing and abstract language theory; (3) Investigate approximation and randomized algorithms for hard automata problems, such as the NFA universality problem. The long term objective and significance is the establishment of new technical tools on word relations that will enrich our body of knowledge on the topic and will enable researchers to employ these tools in their own research programs. Moreover, the proposed research will provide high quality training of HQP.