2017/05/31 by Stefano Crespi Reghizzi, Matteo Pradella
Computer Science · Mathematics · #Abstract family of languages #Arithmetic #Artificial intelligence #Automaton #Closure (psychology) #Computer science #Concatenation (mathematics) #Cone (formal languages) #Context-free language #Discrete mathematics #Fifth-generation programming language #Formal Methods in Verification #Language family #Linguistics #Logic, programming, and type systems #Mathematics #Programming language #Regular language #Rule-based machine translation #Second-generation programming language #Theoretical computer science #cs.FL #semigroups and automata theory
paper · pdf · doi:10.4204/eptcs.252.11
published as EPTCS 252, 2017, pp. 86-100 · In Proceedings AFL 2017, arXiv:1708.06226
openalex publication_date 2017/08/21 · arxiv created 2017/08/22 · arxiv updated 2017/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
Floyd's Operator Precedence (OP) languages are a deterministic context-free family having many desirable properties. They are locally and parallely parsable, and languages having a compatible structure are closed under Boolean operations, concatenation and star; they properly include the family of Visibly Pushdown (or Input Driven) languages. OP languages are based on three relations between any two consecutive terminal symbols, which assign syntax structure to words. We extend such relations to k-tuples of consecutive terminal symbols, by using the model of strictly locally testable regular languages of order k at least 3. The new corresponding class of Higher-order Operator Precedence languages (HOP) properly includes the OP languages, and it is still included in the deterministic (also in reverse) context free family. We prove Boolean closure for each subfamily of structurally compatible HOP languages. In each subfamily, the top language is called max-language. We show that such languages are defined by a simple cancellation rule and we prove several properties, in particular that max-languages make an infinite hierarchy ordered by parameter k. HOP languages are a candidate for replacing OP languages in the various applications where they have have been successful though sometimes too restrictive.