Alternation Hierarchies of First Order Logic with Regular Predicates

DOI10.1007/978-3-319-22177-9_13zbMath1435.03030OpenAlexW2149200336MaRDI QIDQ2947877

Charles Paperman, Luc Dartois

Publication date: 29 September 2015

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://zenodo.org/record/376306

Mathematics Subject Classification ID

Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (3)

The regular languages of wire linear \(\mathrm{AC}^0\) ⋮ Locality and Centrality: The Variety ZG ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Categories as algebra: An essential ingredient in the theory of monoids
• First-order logic and star-free sets
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Logically defined subsets of \(\mathbb{N}{}^ k\)
• Regular languages in \(NC\)
• Finite semigroup varieties of the form V*D
• Dot-depth of star-free events
• Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
• Two-variable first order logic with modular predicates over words
• Linear Automaton Transformations
• Weak Second‐Order Arithmetic and Finite Automata
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• A SYNTACTICAL PROOF OF LOCALITY OF DA
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• On finite monoids having only trivial subgroups

This page was built for publication: Alternation Hierarchies of First Order Logic with Regular Predicates