On the expressive power of FO[+]

DOI10.1007/978-3-642-13089-2_16MaRDI QIDQ3564860zbMATH OpenOpenAlexFDO

Authors Andreas Malcher, Carlo Mereghetti, Beatrice Palano, Christian Choffrut

Publication date 26 May 2010

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13089-2_16

zbMATH Keywords

bounded languagesfirst-order logicsemilinear sets

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive complexity and finite models (68Q19) Formal languages and automata (68Q45)

Recommendations

• First-order logics: some characterizations and closure properties
• First-order definable languages
• STACS 2005
• One quantifier alternation in first-order logic with modular predicates
• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)

Cited in

(4)

• Expressivity of some versions of APAL
• Operator precedence languages: their automata-theoretic and logic characterization
• Bounded fixed-point definability and tabular recognition of languages
• First-order logics: some characterizations and closure properties

This page was built for publication: On the expressive power of FO[+]

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