Hierarchies in fragments of monadic strict NP

Book chapter

Martin, B. and Madelaine, F. 2007. Hierarchies in fragments of monadic strict NP. in: Cooper, B., Löwe, B. and Sorbi, A. (ed.) Computation and logic in the real world: Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007, Proceedings Springer Berlin. Heidelberg.
Chapter titleHierarchies in fragments of monadic strict NP
AuthorsMartin, B. and Madelaine, F.
Abstract

We expose a strict hierarchy within monotone monadic strict NP without inequalities (MMSNP), based on the number of second-order monadic quantifiers. We do this by studying a finer strict hierarchy within a class of forbidden patterns problems (FPP), based on the number of permitted colours. Through an adaptation of a preservation theorem of Feder and Vardi, we are able to prove that this strict hierarchy also exists in monadic strict NP (MSNP). Our hierarchy results apply over a uniform signature involving a single binary relation, that is over digraphs.

Research GroupFoundations of Computing group
Book titleComputation and logic in the real world: Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007, Proceedings
EditorsCooper, B., Löwe, B. and Sorbi, A.
PublisherSpringer Berlin. Heidelberg
SeriesLecture Notes in Computer Science
ISBN
Hardcover9783540730002
Publication dates
Print2007
Publication process dates
Deposited02 Jul 2013
Output statusPublished
Additional information

Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007. Proceedings

Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-540-73001-9_56
LanguageEnglish
Permalink -

https://repository.mdx.ac.uk/item/84279

Log in to edit
  • 19
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as