A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)

DOI10.1016/0020-0190(94)00219-OzbMath0875.68673MaRDI QIDQ673910

Martin Otto

Publication date: 28 February 1997

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

zbMATH Keywords

Finite model theoryCombinatorial problemsDescriptive complexity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Related Items (5)

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

Cites Work

• Classifying regular events in symbolic logic
• On monadic NP vs monadic co-NP
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Monadic generalized spectra
• Unnamed Item
• Unnamed Item

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