2015/01/01 by Violetta Lonati, Dino Mandrioli, Federica Panella +1 · 2 citations
Computer Science · #Formal Methods in Verification #Logic, programming, and type systems #semigroups and automata theory #Computer science #Decidability #Parenthesis #Parsing #Characterization (materials science) #Regular language #Pushdown automaton #Class (philosophy) #Programming language #Büchi automaton #Closure (psychology) #Formal language #Rule-based machine translation #Automaton #Theoretical computer science #Artificial intelligence #Deterministic automaton #Linguistics
paper · doi:10.1137/140978818
openalex publication_date 2015/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26
Operator precedence languages were introduced half a century ago by Robert Floyd to support deterministic and efficient parsing of context-free languages. Recently, we renewed our interest in this class of languages thanks to a few distinguishing properties that make them attractive for exploiting various modern technologies. Precisely, their local parsability enables parallel and incremental parsing, whereas their closure properties make them amenable to automatic verification techniques, including model checking. In this paper we provide a fairly complete theory of this class of languages: we introduce a class of automata with the same recognizing power as the generative power of their grammars; we provide a characterization of their sentences in terms of monadic second-order logic as has been done in previous literature for more restricted language classes such as regular, parenthesis, and input-driven ones; we investigate preserved and lost properties when extending the language sentences from finite length to infinite length (ω-languages). As a result, we obtain a class of languages that enjoys many of the nice properties of regular languages (closure and decidability properties, logic characterization) but is considerably larger than other families---typically parenthesis and input-driven ones---with the same properties, covering “almost” all deterministic languages.