2019  OriginalPaper  Buchkapitel Open Access
Languages Ordered by the Subword Order
1 Introduction

Instead of all words over some alphabet, the universe is a language L.

We add regular predicates or constants to the structure.

Besides the subword order, we also consider the cover relation \(\mathbin {\sqsubset \!\!\!\!\cdot }\).

We add threshold and modulo counting quantifiers to the logic.

The class of regular languages is closed under counting images under unambiguous rational relations.This can be shown either directly or (as we do here) using weighted automata [20].

The proper subword, the cover, and the incomparability relation are unambiguous rational.
2 Preliminaries

\(\mathcal S\models \exists ^{\ge k}x\,\alpha \) iff \(\{w\in L\mid \mathcal S \models \alpha (w)\}\ge k\)

\(\mathcal S\models \exists ^{p \bmod q}x\,\alpha \) iff \(\{w\in L\mid \mathcal S \models \alpha (w)\}\in p+q\mathbb {N}\)

The largest one is \((L,\sqsubseteq ,\mathbin {\sqsubset \!\!\!\!\cdot },(K\cap L)_{K\text { regular}},(w)_{w\in L})\) for some \(L\subseteq \varSigma ^*\). The universe of this structure is the language L, we have two binary predicates (\(\sqsubseteq \) and \(\mathbin {\sqsubset \!\!\!\!\cdot }\)), a unary predicate \(K\cap L\) for every regular language K, and we can use every word from L as a constant.

The other extreme is the structure \((L,\sqsubseteq )\) for some \(L\subseteq \varSigma ^*\) where we consider only the binary predicate \(\sqsubseteq \).

Finally, we will also prove results on the intermediate structure \((L,\sqsubseteq ,(w)_{w\in L})\) that has a binary relation and any word from the language as a constant.
3 The \(\mathrm {FO{+}MOD}\)Theory with Regular Predicates
4 The \(\mathrm {C{+}MOD}\)\(^2\)Theory with Regular Predicates
4.1 Unambiguous Rational Relations

The regular languageis mapped bijectively onto the subword relation.$$ \mathrm {Sub}= \left( \bigcup _{a\in \varSigma }\Bigl (\bigl (\varSigma _2\setminus \{(a,2)\}\bigr )^*\, (a,2)\,(a,1)\Bigr )\right) ^* {\varSigma _2}^*. $$

Let S be the regular language of words from \(\mathrm {Sub}\) with precisely one more occurrence of letters from \(\varSigma _2\) than from \(\varSigma _1\). Then S is mapped bijectively onto the relation \(\mathbin {\sqsubset \!\!\!\!\cdot }\), hence this relation is unambiguous rational.

Similarly, let \(S'\) denote the regular language of all words from \(\mathrm {Sub}\) with at least two more occurrences of letters from \(\varSigma _2\) than from \(\varSigma _1\). It is mapped bijectively onto the relation \(\sqsubset \setminus \mathbin {\sqsubset \!\!\!\!\cdot }\), i.e., \(\sqsubset \setminus \mathbin {\sqsubset \!\!\!\!\cdot }\) is unambiguous rational. \(\square \)

\(u=a_1a_2\dots a_\ell u'\) for some \(\ell \ge 1\), \(a_1,\dots ,a_\ell \in \varSigma \), \(u'\in \varSigma ^*\), and

\(v\in (\varSigma \setminus \{a_1\})^*a_1\,(\varSigma \setminus \{a_2\})^*a_2\cdots (\varSigma \setminus \{a_{\ell 1}\})^*a_{\ell 1}\, (\varSigma \setminus \{a_\ell \})^+ v'\) for some word \(v'\in \varSigma ^*\) with \(u'=v'\).