Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages

DOI10.46298/LMCS-19(4:12)2023arXiv2006.01236MaRDI QIDQ6137830

Stefano Crespi Reghizzi, Matteo Pradella, Dino Mandrioli

Publication date: 16 January 2024

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.01236

zbMATH Keywords

first-order logicaperiodicityvisibly pushdown languagesinput-driven languagesoperator precedence languagesstar-free expressionsstructured languages

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Model-checking structured context-free languages
• A descriptive characterisation of linear languages
• Modulo-counting quantifiers over finite trees
• Generalizing input-driven languages: theoretical and practical benefits
• Operator precedence and the visibly pushdown property
• Star-freeness, first-order definability and aperiodicity of structured context-free languages
• Beyond operator-precedence grammars and languages
• Operator precedence temporal logic and model checking
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Colored Nested Words
• Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization
• Piecewise testable tree languages
• Visibly Linear Temporal Logic
• First-Order Logic Definability of Free Languages
• A decidable characterization of locally testable tree languages
• Weak Second‐Order Arithmetic and Finite Automata
• Adding nesting structure to words
• Counter-Free Input-Determined Timed Automata
• Aperiodicity in Tree Automata
• Height-Deterministic Pushdown Automata
• FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES
• Synchronization of Pushdown Automata
• First-Order and Temporal Logics for Nested Words
• Decision Problems of Finite Automata Design and Related Arithmetics
• On ω-regular sets
• Operator Precedence Grammars and the Noncounting Property
• First-order properties of trees, star-free expressions, and aperiodicity
• Algebraic properties of operator precedence languages
• Noncounting Context-Free Languages
• First-order logic on finite trees
• Syntactic Analysis and Operator Precedence
• Parsing Techniques
• A Proof of Kamp's theorem
• Parenthesis Grammars
• The use of grammatical inference for designing programming languages

This page was built for publication: Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages