A descriptive characterisation of even linear languages (Q1430213)

The Büchi-Elgot-Trakhtenbrot Theorem states that the regular languages are exactly those that can be defined by formulas of monadic second-order predicate logic with equality having predicate symbols \(S\) for successor and \(Q_a\) for every terminal letter \(a\) (informally stated with the semantics that \(Q_a(x)\) states that at position \(x\) in the input word we find letter \(a\)). Linear languages are context-free languages that have a linear grammar, i.e., a context-free grammar in which every production has just one variable on the right hand side. Even linear languages are those linear languages, that have linear grammars in which in every production to the right and left of the nonterminal on the right hand side the same number of terminal symbols appear. Obviously, the closure of even linear languages under homomorphism yields the linear languages. A characterization of the even linear languages reminescent of the Myhill-Nerode characterization of the regular languages allows the conclusion that every regular language is even linear. The present paper gives a model-theoretic characterization of the class of even linear languages in the sense of Büchi, Elgot, and Trakhtenbrot: A language is even linear if and only if it is definable by a formula of monadic second-order predicate logic with equality having predicate symbols \(Q_a\) for every terminal letter \(a\) and, instead of successor as above, a symbol for the binary relation that, in a word of length \(n\) contains a pair \((i,j)\) iff \(i<j\) and to the left of \(i\) we find as many position in the input word as to the right of \(j\).