Operator precedence ω-languages

Omega-languages are becoming more and more relevant nowadays when most applications are "ever-running”. Recent literature, mainly under the motivation of widening the application of model checking techniques, extended the analysis of these languages from the simple regular ones to various classes of languages with "visible structure", i.e., languages whose syntax structure is immediately visible in their strings, such as visibly pushdown languages (VPLs). Floyd’s operator precedence languages (FLs), instead, where defined with the original motivation of supporting deterministic parsing. These seemingly unrelated classes of languages exhibit interesting relations: precisely FLs, which strictly include VPLs, enjoy all relevant closure properties. FLs have also been characterized in terms of a suitable automata family and in terms of a logic notation. In this paper we introduce Floyd Omega-languages (FOmegaLs); we investigate their expressiveness depending on various acceptance criteria and their closure properties. Whereas some properties are natural extensions of those holding for regular languages, others required novel investigation techniques. A simple application-oriented example shows the considerable gain in expressiveness and verifiability offered by FOLs w.r.t. previous classes.