First-order logics: some characterizations and closure properties

DOI10.1007/S00236-012-0157-ZMaRDI QIDQ715044zbMATH OpenOpenAlexFDO

Authors Christian Choffrut, Andreas Malcher, Carlo Mereghetti, 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

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)

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

Cites work

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

Cited in

(11)

• Weighted operator precedence languages
• CIFOL: case-intensional first order logic. I: Toward a theory of sorts
• First-order definable languages
• Dyck Words, Pattern Avoidance, and Automatic Sequences
• scientific article; zbMATH DE number 1440090 (Why is no real title available?)
• Dyck words, pattern avoidance, and automatic sequences
• Undecidability of satisfiability of expansions of \(\mathrm{FO}[<]\) over words with a \(\mathrm{FO}[+]\)-definable set
• On the expressive power of FO[+]
• Characterization and complexity results on jumping finite automata
• Weighted operator precedence languages
• Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization

Describes a project that uses

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)