---
res:
bibo_abstract:
- "The monotonicity checking problem is a sorting-type problem defined as: Given
a finite poset and an unknown real-valued function on it, find out whether this
function is order preserving.\r\nWe investigate the worst case behaviour of decision
monotonicity checking algorithms. Two models are considered: the comparison model
and the linear model.\r\nIn the comparison model the queries are pairwise comparisons
of values of the function. We get some general bounds on monotonicity checking
complexity and analyse the dependence of the complexity of monotonicity checking
on certain type of combinatorial operations on posets.\r\nWe determine the monotonicity
checking complexity of the ranked poset in which every two elements of different
rank are comparable and get nontrivial lower and upper bounds on the complexity
of monotonicity checking of the Boolean lattice. Also, we investigate monotonicity
checking of functions that take a \"small\" number of different values and determine
the monotonicity checking complexity of Boolean functions.\r\nThe queries in this
model are comparisons of linear combinations of the values of the input function.
We consider a geometric interpretation of monotonicity checking and give a method
for establishing lower bounds on the complexity of monotonicity checking in the
linear model using this interpretation. We use this method to establish a lower
bound on the monotonicity checking complexity of a particular poset. As a consequence,
we get a lower bound on the complexity of simultaneous determination of the minimum
and the maximum of a sequence of real numbers.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Marina
foaf_name: Kyureghyan, Marina
foaf_surname: Kyureghyan
dct_date: 2004^xs_gYear
dct_language: eng
dct_publisher: Bielefeld University@
dct_subject:
- Halbgeordnete Menge , Monotone Funktion , Sortierverfahren , KomplexitÃ¤t , Entscheidungsbaum
, Sortieren , Monotonie , KomplexitÃ¤t , Linearer Entscheidungsbaum , Sorting ,
Monotonicity , Recognition complexity , Linear decision tree
dct_title: Monotonicity checking@
...