First-order logics: some characterizations and closure properties

DOI10.1007/S00236-012-0157-ZzbMATH Open1279.68143OpenAlexW1975359072MaRDI QIDQ715044FDOQ715044

Carlo Mereghetti, Christian Choffrut, Andreas Malcher, Beatrice Palano

Publication date: 15 October 2012

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-012-0157-z

Recommendations

• On the expressive power of FO[+]
• First-order definable languages
• One quantifier alternation in first-order logic with modular predicates
• First-order logic on finite trees
• Fragments of first-order logic over infinite words

zbMATH Keywords

recognition\(\mathrm{FO}[+\)-definable languages]semilinear languagesword bounded languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• Title not available (Why is that?)
• Bounded Algol-Like Languages
• Parity, circuits, and the polynomial-time hierarchy
• Title not available (Why is that?)
• The descriptive complexity approach to LOGCFL
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Weak Second‐Order Arithmetic and Finite Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting quantifiers, successor relations, and logarithmic space
• Some subclasses of context-free languages in \(NC^ 1\)
• Simple matrix languages
• Expressibility and Parallel Complexity
• On tape-bounded complexity classes and multihead finite automata
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• On the relative complexity of some languages in \(NC^ 1\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$

Cited In (8)

• CIFOL: case-intensional first order logic. I: Toward a theory of sorts
• Dyck Words, Pattern Avoidance, and Automatic Sequences
• Title not available (Why is that?)
• Dyck words, pattern avoidance, and automatic sequences
• Weighted Operator Precedence Languages
• Characterization and complexity results on jumping finite automata
• Weighted operator precedence languages
• Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization

Uses Software

• ALGOL 60

This page was built for publication: First-order logics: some characterizations and closure properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715044)