Undecidability of satisfiability of expansions of FO[<] over words with a FO[+]-definable set

DOI10.3233/COM-170069zbMATH Open1420.03103MaRDI QIDQ4601030FDOQ4601030

Authors: Arthur Milchior 

Publication date: 18 January 2018

Published in: Computability (Search for Journal in Brave)

Recommendations

• First-order definable languages
• Two-variable first order logic with counting quantifiers: complexity results
• First-order logics: some characterizations and closure properties
• scientific article; zbMATH DE number 7297889
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS

zbMATH Keywords

finite model theoryfirst-order logicarithmeticundecidability

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Undecidability and degrees of sets of sentences (03D35)

Cited In (1)

• Spectra and satisfiability for logics with successor and a unary function

This page was built for publication: Undecidability of satisfiability of expansions of \(\mathrm{FO}[<]\) over words with a \(\mathrm{FO}[+]\)-definable set

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