scientific article; zbMATH DE number 2079027

MaRDI QIDQ4474839zbMATH OpenFDO

Authors Etienne Grandjean, Frédéric Olive

Publication date 21 July 2004

zbMATH Keywords

computational complexityfinite model theorylinear timemonadic second-order logicnondeterminismNP-complete problemrandom access machine

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Monadic logical definability of nondeterministic linear time
• On monadic NP vs monadic co-NP
• STACS 2004
• scientific article; zbMATH DE number 1424044
• Monotonicity and the Expressibility of NP Operators

Cited in

(11)

• Monadic logical definability of nondeterministic linear time
• A descriptive complexity approach to the linear hierarchy.
• Sorting, linear time and the satisfiability problem
• scientific article; zbMATH DE number 6387492 (Why is no real title available?)
• SAT in Monadic Gödel Logics: A Borderline between Decidability and Undecidability
• Logical Description of Monotone NP Problems
• Rudimentary Languages and Second‐Order Logic
• scientific article; zbMATH DE number 1424044 (Why is no real title available?)
• Monotone recursive definition of predicates and its realizability interpretation
• STACS 2004
• Complete problems for monotone NP

This page was built for publication:

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