Recognition of order-preserving maps

DOI10.1007/BF00337922MaRDI QIDQ1063048zbMATH OpenOpenAlexFDO

Publication date 1985

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00337922

algorithms finite ordered sets monotone mapping

Exact enumeration problems, generating functions (05A15) Partial orders, general (06A06) Discrete mathematics in relation to computer science (68R99)

Review text

Let P, Q be finite ordered sets and \(f: P\to Q\) be a monotone mapping. For a given algorithm A whose elementary steps are the evaluations of f on elements of P let \(\phi\) (A,f) be the number of steps of A which are necessary to know f. Further, put \(\phi (P,Q)=\min \max \phi (A,f)\); the maximum taken over all f's and minimum over all algorithms A. The author finds lower bounds and upper bounds for the number \(\phi\) (P,Q) and determines this number exactly in some special cases.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Recognition of order-preserving maps

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