Non-crossing, leftwards directed contingency functions on strings

Abstract

The results presented in this thesis are small additions to the field known as the theory of formal languages. The central theme is logical characterisations of language classes using contingency functions on strings, that is, a map between the positions of a string of letters. The language class definable by each of several logics over a special noncrossing type of these functions is explored, and a new kind of finite-state automaton is defined.

The concept of contingency functions is derived from similar work by Tore Langholm on contingency functions on trees. Inspired by his results, the contingency function is subjected to a non-crossing, leftwards directed (NCL) constraint. A related concept, matchings on strings, conceived by Lautemann, Schwentick and Therien, is also discussed and their results are used in the first part of the thesis.

The first chapters present the field and define the necessary concepts. Then the relations between language classes each definable as the set of strings of the set of models of sentences consisting of one single existential quantifier over contingency functions satisfying NCL in front of a formula in either first-order or monadic second-order logic using either a successor relation or a natural order relation. All the classes are shown to be equal to each other and the class of context-free languages.

A new variety of the finite-state automaton, the NCL-automaton, is introduced, having additional restrictions on the admissible transitions based on non-crossing contingency functions. A pumping lemma for the language class recognised by NCL-automata is shown. This class is then shown to be equal to the language class described by sentences consisting of one single existential quantifier over contingency functions satisfying NCL in front of a formula in existential monadic second order logic with a successor function. The language class recognised by NCL-automata is shown to lie strictly between the regular and context-free language classes. Lastly, some closure properties of the language class recognised by NCL-automata are demonstrated.

The thesis shows that there is a difference in the complexity of the definable language classes between logics including a two-place predicate in the signature, either successor relation or equality suffices, and a logic using only one-place functions. The former logic is able to capture the context-free languages when existential quantification over a single binary second-order relation is permitted, the weaker logic captures a smaller class.