First-order logics: some characterizations and closure properties
From MaRDI portal
Publication:715044
DOI10.1007/s00236-012-0157-zzbMath1279.68143OpenAlexW1975359072MaRDI QIDQ715044
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
recognition\(\mathrm{FO}[+\)-definable languages]semilinear languagesword bounded languages
Related Items (5)
Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization ⋮ Dyck Words, Pattern Avoidance, and Automatic Sequences ⋮ Weighted operator precedence languages ⋮ Weighted Operator Precedence Languages ⋮ Characterization and complexity results on jumping finite automata
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Some subclasses of context-free languages in \(NC^ 1\)
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On the relative complexity of some languages in \(NC^ 1\)
- On uniform circuit complexity
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- On tape-bounded complexity classes and multihead finite automata
- Counting quantifiers, successor relations, and logarithmic space
- On uniformity within \(NC^ 1\)
- Weak Second‐Order Arithmetic and Finite Automata
- Parity, circuits, and the polynomial-time hierarchy
- Expressibility and Parallel Complexity
- Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
- Bounded Algol-Like Languages
- Simple matrix languages
- The descriptive complexity approach to LOGCFL
This page was built for publication: First-order logics: some characterizations and closure properties
