Non-regular complexity

Abstract: Given a computational model A, we will call another model B an extension of A if computation steps possible in a system (machine, grammar, etc.) of type A are also possible in systems of type B and the latter allow some operations that are not possible in the former. Such a relationship between models is exhibited by context-free grammars as extensions of regular grammars, or one-way jumping automata and automata with translucent letters as extensions of finite automata. The operations available in the extensions but not in the original model can be viewed as a computational resource and hence can be analyzed quantitatively, similarly to computational complexity theory. Recent years saw both the continuation of lines of inquiry from decades ago, counting the non-regular rules used in context-free derivations (Bordihn and Mitrana, '20), and the start of new ones, counting the number of jumps/sweeps used during computations with the aforementioned extended automata models (Fazekas and Mercaş, '22-23, Mitrana et al., '24). As the base model in all three cases generates/accepts the class of regular languages, the complexity notions introduced can be viewed as a measure of how non-regular a machine, grammar or language is. In this talk I give an overview of the research concerning the hierarchies of language classes defined through these non-regular complexity measures, and propose some questions for further investigation.

formal languages and automata theory

Audience: researchers in the topic

( slides | video )

One FLAT World Seminar