Generalizing input-driven languages: theoretical and practical benefits

DOI10.1016/j.cosrev.2017.12.001zbMath1382.68136arXiv1705.00984OpenAlexW2963802901MaRDI QIDQ1706605

Matteo Pradella, Dino Mandrioli

Publication date: 22 March 2018

Published in: Computer Science Review (Search for Journal in Brave)

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

zbMATH Keywords

monadic second-order logicdecidabilityclosure propertiescontext-free languagesregular languagesautomatic verificationvisibly pushdown languagesinput-driven languagesoperator-precedence languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items

Model-checking structured context-free 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 ⋮ Operator precedence temporal logic and model checking ⋮ Unnamed Item ⋮ Annotated regular expressions and input-driven languages

Uses Software

• MONA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weighted automata and logics for infinite nested words
• A theory of timed automata
• Generalizing input-driven languages: theoretical and practical benefits
• Operator precedence and the visibly pushdown property
• On infinite transition graphs having a decidable monadic theory
• The complexity of first-order and monadic second-order logic revisited
• Weighted automata and weighted logics
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• What makes some language theory problems undecidable
• Colored Nested Words
• WEIGHTED NESTED WORD AUTOMATA AND LOGICS OVER STRONG BIMONOIDS
• Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization
• Precedence Automata and Languages
• First-Order Logic Definability of Free Languages
• Weak Second‐Order Arithmetic and Finite Automata
• On the definition of a family of automata
• Adding nesting structure to words
• Height-Deterministic Pushdown Automata
• Visibly pushdown languages
• Synchronization of Pushdown Automata
• First-Order and Temporal Logics for Nested Words
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Decision Problems of Finite Automata Design and Related Arithmetics
• Algebraic properties of operator precedence languages
• Weighted Operator Precedence Languages
• Syntactic Analysis and Operator Precedence
• Parsing Techniques
• Some properties of precedence languages
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Parenthesis Grammars
• Semantics of context-free languages
• An axiomatic basis for computer programming
• On the translation of languages from left to right
• The use of grammatical inference for designing programming languages
• Bounded context syntactic analysis
• Formal languages and compilation

This page was built for publication: Generalizing input-driven languages: theoretical and practical benefits