id,collection,dc.contributor.author,dc.date.accessioned,dc.date.available,dc.date.issued,dc.description.abstract[de],dc.format.extent,dc.identifier.uri,dc.language,dc.relation.ispartofseries,dc.rights.uri,dc.subject.ddc,dc.title,dc.type,dcterms.accessRights.openaire,refubium.affiliation.other,refubium.affiliation[de],refubium.mycore.derivateId,refubium.mycore.fudocsId,refubium.resourceType.isindependentpub,refubium.series.name,refubium.series.reportNumber "427f4364-e84d-4b9b-97ec-e733f0f9f644","fub188/17746","Felsner, Stefan||Wagner, Dorothea","2018-06-08T07:52:05Z","2009-10-22T12:18:56.779Z","1999","The recognition complexity of ordered set properties is considered, i.e. how many questions have to be asked to decide if an unknown ordered set has a prescribed property. We prove a lower bound of Ω (n²) for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable paris we show that the recogintion complexity is (n:2); the complexity of interval orders is exactly (n:2) -1. Non-trivial upper bounds are given for being a lattice, containing a chain of length k ≥ 2 and having width k.","13 S.","https://refubium.fu-berlin.de/handle/fub188/18884||http://dx.doi.org/10.17169/refubium-22565","eng","urn:nbn:de:kobv:188-fudocsseries000000000021-2","http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen","500 Naturwissenschaften und Mathematik::510 Mathematik","On the complexity of partial order properties","Arbeitspapier","open access","Institut für Informatik:::6dd1f8be-8a6d-4a4a-8f8d-572eb83788da:::600","Mathematik und Informatik","FUDOCS_derivate_000000000769","FUDOCS_document_000000004025","no","Freie Universität Berlin, Fachbereich Mathematik und Informatik","99-19"