Grant: Discovery Grants Program - Individual

The descriptional complexity of an object is usually the shortest description of that object. For example, a possible descriptional complexity using natural languages could be the minimum number of words or letters necessary to describe the object. In computer science we use programs to describe objects, and the minimum "size" of all these programs is the descriptional complexity of the given object. We use various descriptions to represent an object in the memory of a computer. Each description follows rules, and is part of a formal language. The language and its representation form a formal system. My research includes the study of formal systems, their descriptional complexity, and the decriptional complexity of all possible operations using such systems. I am looking into defining new formal systems for a variety of classes of formal languages with computable descriptional complexity. A possible application of formal language theory is for languages describing different categories of messages. For example, let us consider the language of SPAM. In order to recognize SPAM, mail filters make use of a special form of regular expressions, called regex. All newer programming languages have regex libraries or built-in regex instructions. I gave a formal treatment for these types of languages and introduced alternative formal systems in order to have uniform implementations. Since these expressions introduce a high degree of non-determinism in implementations, I will study how to improve the efficiency and size complexity for various implementations. In particular, I will focus on the non-determinism of the implemented system and on other possible improvements, like using cover languages. Statistical tests and other experimental tools will be used. I am considering involving my students to implement the formal systems and algorithms. The results of this theoretical research may have applications in compilers, bio-computing, and cryptography.