Monotonicity checking

Kyureghyan M (01T00:00:00Z.01.1970)
Bielefeld (Germany): Bielefeld University.

Bielefelder E-Dissertation| Englisch
 
Download
OA
Autor/in
Kyureghyan, Marina
Betreuer
Ahlswede, Rudolf (Prof. Dr. Dr. h.c.)
Alternativer Titel
Monotonie-Überprüfung
Abstract / Bemerkung
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. We investigate the worst case behaviour of decision monotonicity checking algorithms. Two models are considered: the comparison model and the linear model. In 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. We 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. The 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.
Stichworte
Halbgeordnete Menge , Monotone Funktion , Sortierverfahren , Komplexität , Entscheidungsbaum , Sortieren , Monotonie , Komplexität , Linearer Entscheidungsbaum , Sorting , Monotonicity , Recognition complexity , Linear decision tree
Jahr
2004
Page URI
https://pub.uni-bielefeld.de/record/2303437

Zitieren

Kyureghyan M. Monotonicity checking. Bielefeld (Germany): Bielefeld University; 2004.
Kyureghyan, M. (01T00:00:00Z.01.1970). Monotonicity checking. Bielefeld (Germany): Bielefeld University.
Kyureghyan, M. 01T00:00:00Z.01.1970 Monotonicity checking. Bielefeld (Germany): Bielefeld University.
Kyureghyan, M., 01T00:00:00Z.01.1970 Monotonicity checking, Bielefeld (Germany): Bielefeld University.
M. Kyureghyan, Monotonicity checking, Bielefeld (Germany): Bielefeld University, 2004.
Kyureghyan, M.: Monotonicity checking. Bielefeld University, Bielefeld (Germany) (2004).
Kyureghyan, Marina. Monotonicity checking. Bielefeld (Germany): Bielefeld University, 2004.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T08:57:43Z
MD5 Prüfsumme
a84783179d51e518bee5539ff71de0c0

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar