Show simple item record

dc.contributor.authorEiter, Thomas
dc.contributor.authorGottlob, Georg
dc.contributor.authorGurevich, Yuri
dc.date.accessioned2022-09-12T09:38:45Z
dc.date.available1998-07-08T22:00:00Z
dc.date.available2022-09-12T09:38:45Z
dc.date.issued1997
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-257
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7563
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-6997
dc.description.abstractExistential second­order logic (ESO) and monadic second­order logic (MSO) have attracted much interest in logic and computer science. ESO is a much more expressive logic over word structures than MSO. However, little was known about the relationship between MSO and syntactic fragments of ESO. We shed light on this issue by completely characterizing this relationship for the prefix classes of ESO over strings, (i.e., finite word structures). Moreover, we determine the complexity of model checking over strings, for all ESO­prefix classes. Let ESO(Q) denote the prefix class containing all sentences of the shape 9RQ' where R is a list of predicate variables, Q is a first­order quantifier prefix from the prefix set Q, and ' is quantifier free. We show that ESO(9 \Lambda 89 \Lambda ) and ESO(9 \Lambda 88) are the maximal standard ESO­prefix classes contained in MSO, thus expressing only regular languages. We further prove the following dichotomy theorem: An ESO prefix­class either expresses only regular languages (and is thus in MSO), or it expresses some NP­complete languages. We also give a precise characterization of those ESO­prefix classes which are equivalent to MSO over strings, and of the ESO­prefix classes which are closed under complementation on strings.en
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 9702 / 1997
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subject.ddcddc:004de_DE
dc.titleExistential second-order logic over stringsen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.id25
local.opus.instituteInstitut für Informatikde_DE
local.opus.fachgebietInformatikde_DE


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

In Copyright