A note on the number of monadic quantifiers in monadic ^1_1

DOI10.1016/0020-0190(94)00219-OMaRDI QIDQ673910zbMATH OpenFDO

Authors Martin Otto

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)00219-O

zbMATH Keywords

Combinatorial problemsDescriptive complexityFinite model theory

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Cites work

• Classifying regular events in symbolic logic
• Decision Problems of Finite Automata Design and Related Arithmetics
• scientific article; zbMATH DE number 3885853 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• Monadic generalized spectra
• On monadic NP vs monadic co-NP
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(5)

• The closure of monadic NP
• Arity and alternation: a proper hierarchy in higher order logics
• The monadic quantifier alternation hierarchy over grids and graphs
• One unary function says less than two in existential second order logic
• A logical approach to locality in pictures languages

This page was built for publication: A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)

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