Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization

DOI10.1137/140978818OpenAlexW1078917731WikidataQ57318719 ScholiaQ57318719MaRDI QIDQ2944566

Matteo Pradella, Federica Panella, Dino Mandrioli, Violetta Lonati

Publication date: 2 September 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2434/352809

zbMATH Keywords

monadic second-order logic\(\omega\)-languagesvisibly pushdown languagesoperator precedence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (16)

Model-checking structured context-free languages ⋮ Locally Chain-Parsable Languages ⋮ Beyond operator-precedence grammars and languages ⋮ Verification of programs with exceptions through operator precedence automata ⋮ Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages ⋮ Generalizing input-driven languages: theoretical and practical benefits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Operator precedence temporal logic and model checking ⋮ Temporal logics with language parameters ⋮ Toward a theory of input-driven locally parsable languages ⋮ Unnamed Item ⋮ Monoid-Based Approach to the Inclusion Problem on Superdeterministic Pushdown Automata ⋮ Weighted operator precedence languages ⋮ Weighted automata ⋮ Weighted Operator Precedence Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-order logics: some characterizations and closure properties
• Adherences of languages
• Operator precedence and the visibly pushdown property
• Parallel parsing of operator precedence grammars
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Logic Characterization of Invisibly Structured Languages: The Case of Floyd Languages
• Precedence Automata and Languages
• First-Order Logic Definability of Free Languages
• Adding nesting structure to words
• Synchronization of Grammars
• Height-Deterministic Pushdown Automata
• On the Expressive Power of FO[ + ]
• Visibly pushdown languages
• First-Order and Temporal Logics for Nested Words
• PDL for ordered trees
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Algebraic properties of operator precedence languages
• Model-Checking Parse Trees
• Operator Precedence ω-Languages
• Syntactic Analysis and Operator Precedence
• Parsing Techniques
• Some properties of precedence languages
• Parenthesis Grammars
• The minimalization of tree automata
• Testing and generating infinite sequences by a finite automaton
• On the translation of languages from left to right
• The use of grammatical inference for designing programming languages

This page was built for publication: Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization