TY - JOUR A1 - Zheng, Xizhong T1 - Recursive approximability of real numbers KW - computable reals KW - semi-computable reals KW - weakly computable reals KW - recursively approximable realy Y1 - 2002 ER - TY - JOUR A1 - Zheng, Xizhong T1 - Closure properties on real numbers under limits and computable operators KW - weakly computable reals KW - computable real functions KW - closure properties Y1 - 2002 ER - TY - JOUR A1 - Rettinger, Robert A1 - Zheng, Xizhong A1 - Gengler, Romain A1 - Braunmühl, Burchard von T1 - Monotonically computable real numbers Y1 - 2002 ER - TY - GEN A1 - Zheng, Xizhong A1 - Rettinger, Robert A1 - Braunmühl, Burchard von T1 - Effectively absolute continuity and effective Jordan decomposability T2 - Electronic Notes in Theoretical Computer Science Y1 - 2002 SN - 1571-0661 N1 - Proceedings of CCA 2002, July 12 - 13, Malaga, Spain VL - 66 IS - 1 SP - 213 EP - 224 ER - TY - CHAP A1 - Rettinger, Robert A1 - Zheng, Xizhong A1 - Braunmühl, Burchard von ED - Oscar, H. Ibarra T1 - Computable Real Functions of Bounded Variation and semi-Computable Real Numbers T2 - Computing and combinatorics, 8th annual international conference, COCOON 2002, Singapore, August 15 - 17, 2002 Y1 - 2002 SN - 3-540-43996-X SP - 47 EP - 56 PB - Springer CY - Berlin [u.a.] ER - TY - RPRT A1 - Zheng, Xizhong A1 - Rettinger, Robert A1 - Braunmühl, Burchard von T1 - On the Jordan decomposability for computable functions of bounded variation KW - Jordansche Zerlegung KW - Zerlegung Y1 - 2002 PB - BTU, Inst. of Computer Science CY - Cottbus ER - TY - GEN A1 - Zheng, Xizhong A1 - Weihrauch, Klaus T1 - The arithmetical hierarchy of real numbers T2 - Mathematical Logic Quarterly Y1 - 2001 SN - 0942-5616 VL - 47 IS - 1 SP - 51 EP - 65 ER - TY - CHAP A1 - Rettinger, Robert A1 - Gengler, Romain A1 - Zheng, Xizhong A1 - Braunmühl, Burchard von T1 - Monotonically Computable Real Numbers T2 - Combinatorics, computability and logic, proceedings of the Third International Conference on Combinatorics, Computability and Logic, (DMTCS '01) Y1 - 2001 SN - 1-85233-526-2 SP - 187 EP - 202 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Rettinger, Robert A1 - Zheng, Xizhong T1 - Hierarchy of monotonically computable real numbers T2 - Mathematical foundations of computer science 2001, 26th international symposium, Mariánské Lázně, Czech Republic, August 27 - 31, 2001 Y1 - 2001 SN - 3-540-42496-2 SP - 633 EP - 644 PB - Springer CY - Berlin [u.a.] ER - TY - GEN A1 - Zheng, Xizhong A1 - Rettinger, Robert T1 - Effective Jordan decomposition T2 - Theory of Computing System Y1 - 2005 SN - 1432-4350 VL - 38 IS - 2 SP - 189 EP - 209 ER - TY - CHAP A1 - Rettinger, Robert A1 - Zheng, Xizhong ED - Cooper, Stuart Barry T1 - On the Turing degrees of divergence bounded computable reals T2 - New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005 Y1 - 2005 SN - 3-540-26179-6 SP - 418 EP - 428 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Zheng, Xizhong T1 - On the hierarchy of Delta_02-numbers Y1 - 2004 UR - http://www.informatik.uni-trier.de/Reports/TR-08-2004/rnc6_15_zheng.pdf ER - TY - CHAP A1 - Zheng, Xizhong A1 - Rettinger, Robert T1 - A note on the Turing degrees of divergence bounded computable reals Y1 - 2004 ER - TY - CHAP A1 - Zheng, Xizhong A1 - Rettinger, Robert T1 - On the extensions of Solovay Reducibility Y1 - 2004 ER - TY - CHAP A1 - Zheng, Xizhong A1 - Rettinger, Robert A1 - Gengler, Romain ED - Rovan, Branislav T1 - Ershov's hierarchy of real numbers T2 - Mathematical foundations of computer science 2003, 28th international symposium MFCS, Bratislava, Slovakia, August 25 - 29, 2003 Y1 - 2003 SN - 3-540-40671-9 SP - 681 EP - 690 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Zheng, Xizhong T1 - On the divergence bounded computable real numbers Y1 - 2003 ER - TY - CHAP A1 - Zheng, Xizhong A1 - Barmpalias, George T1 - On the monotonic computability of semi-computable real numbers Y1 - 2003 ER - TY - CHAP A1 - Zheng, Xizhong A1 - Rettinger, Robert A1 - Braunmühl, Burchard von T1 - On the effective Jordan decomposability Y1 - 2003 ER - TY - CHAP A1 - Rettinger, Robert A1 - Zheng, Xizhong A1 - Gengler, Romain A1 - Braunmühl, Burchard von T1 - Weakly computable real numbers and total computable real functions Y1 - 2001 ER - TY - JOUR A1 - Zheng, Xizhong A1 - Rettinger, Robert A1 - Barmpalias, George T1 - h-Monotonically computable real numbers JF - Mathematical Logic Quarterly Y1 - 2005 SN - 0942-5616 VL - 51 IS - 2 SP - 157 EP - 170 ER - TY - GEN A1 - Zheng, Xizhong A1 - Rettinger, Robert T1 - Weak computability and representation of real numbers T2 - Mathematical Logic Quarterly Y1 - 2004 SN - 0942-5616 VL - 50 IS - 4/5 SP - 431 EP - 442 ER - TY - GEN A1 - Rettinger, Robert A1 - Zheng, Xizhong T1 - On the hierarchy and extension of monotonically computable real numbers T2 - Journal of Complexity Y1 - 2003 SN - 0885-064X VL - 19 IS - 5 SP - 672 EP - 691 ER - TY - GEN A1 - Zheng, Xizhong T1 - On the Turing degrees of weakly computable real numbers T2 - Journal of Logic and Computation Y1 - 2003 SN - 0955-792X VL - 13 IS - 2 SP - 159 EP - 172 ER - TY - GEN A1 - Ambos-Spies, Klaus A1 - Weihrauch, Klaus A1 - Zheng, Xizhong T1 - Weakly computable real numbers T2 - Journal of Complexity Y1 - 2000 SN - 0885-064X VL - 16 IS - 4 SP - 676 EP - 690 ER - TY - GEN A1 - Weihrauch, Klaus A1 - Zheng, Xizhong T1 - Computability on Continuous, Lower Semi-Continuous and Upper Semi-Continuous Real Functions T2 - Theoretical Computer Science Y1 - 2000 VL - 234 IS - 1-2 SP - 109 EP - 133 ER - TY - JOUR A1 - Zheng, Xizhong T1 - Closure properties of real numbers classes under CBV functions Y1 - 2005 ER - TY - JOUR A1 - Zheng, Xizhong T1 - Divergence bounded computable real numbers Y1 - 2006 ER - TY - CHAP A1 - Rettinger, Robert A1 - Zheng, Xizhong ED - Wang, Lusheng T1 - Solovay reducibility on d-c.e. real numbers T2 - Computing and combinatorics, 11th annual international conference, COCOON 2005, Kunming, China, August 16 - 29, 2005 Y1 - 2005 SN - 978-3-540-28061-3 SP - 359 EP - 368 PB - Springer CY - Berlin [u.a.] ER - TY - GEN A1 - Rettinger, Robert A1 - Zheng, Xizhong T1 - A hierarchy of Turing degrees of divergence bounded computable real numbers T2 - Journal of Complexity Y1 - 2006 VL - 22 IS - 6 SP - 818 EP - 826 ER - TY - JOUR A1 - Chen, Q. A1 - Su, K. A1 - Zheng, Xizhong T1 - Primitive Recursive Real Numbers Y1 - 2007 ER - TY - JOUR A1 - Chen, Q. A1 - Rettinger, Robert A1 - Su, K. A1 - Sattar, A. A1 - Yue, W. A1 - Lu, G. A1 - Zheng, Xizhong T1 - Verification of Authentication Protocols for Epistemic Goals via SAT Compilation Y1 - 2006 ER - TY - JOUR A1 - Chen, Q. A1 - Su, K. A1 - Yue, W. A1 - Zheng, Xizhong T1 - Instantiation Space: A New Model for Security Protocol Logic Y1 - 2006 ER - TY - GEN A1 - Zheng, Xizhong T1 - Classification of the Computable Approximations T2 - Electronic Notes in Theoretical Computer Science Y1 - 2007 SN - 1571-0661 VL - 167 SP - 325 EP - 344 ER - TY - GEN A1 - Chen, Qingliang A1 - Su, Kaile A1 - Zheng, Xizhong T1 - Primitive Recursiveness of Real Numbers under Different Representations T2 - Electronic Notes in Theoretical Computer Science Y1 - 2007 SN - 1571-0661 VL - 167 SP - 303 EP - 324 ER - TY - CHAP A1 - Su, Kaile A1 - Chen, Qingliang A1 - Zheng, Xizhong A1 - Yue, Weiya T1 - Reasoning about Knowledge by SAT Solving T2 - International Conference on Computational Intelligence and Security, CIS 2006, 3 - 6 Nov. 2006, Guangzhou, China Y1 - 2006 SN - 1-4244-0604-8 SN - 1-4244-0605-6 SP - 536 EP - 539 PB - IEEE Press CY - Piscataway, NJ ER - TY - CHAP A1 - Zheng, Xizhong T1 - A Computability Theory of Real Numbers T2 - Logical approaches to computational barriers, second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings Y1 - 2006 SN - 3-540-35466-2 SP - 584 EP - 594 PB - Springer CY - Berlin [u.a.] ER - TY - JOUR A1 - Zheng, Xizhong T1 - On the Hierarchies of Delta 0_2 real Numbers Y1 - 2007 ER - TY - JOUR A1 - Downey, Rod A1 - Wu, D. A1 - Zheng, Xizhong T1 - Degrees of d.c.e. Reals Y1 - 2004 ER - TY - THES A1 - Zheng, Xizhong T1 - Effective Hierarchy of Real Numbers Y1 - 2007 SN - 978-3-8322-6343-0 PB - Shaker CY - Aachen ER - TY - CHAP A1 - Zheng, Xizhong T1 - Bounded Computable Enumerability and Hierarchy of Computably Enumerable Reals Y1 - 2007 ER - TY - GEN A1 - Meer, Klaus T1 - Complexity aspects of a semi-infinite optimization problem T2 - Optimization : a Journal of Mathematical Programming and Operations Research Y1 - 2008 SN - 1029-4945 SN - 0233-1934 VL - 57 IS - 1 SP - 143 EP - 152 ER - TY - GEN A1 - Meer, Klaus A1 - Rautenbach, Dieter T1 - On the OBDD size for graphs of bounded tree- and clique-width Y1 - 2009 ER - TY - GEN A1 - Meer, Klaus A1 - Ziegler, Martin T1 - An explicit solution to Post's problem over the reals T2 - Journal of Complexity Y1 - 2008 SN - 0885-064x VL - 24 IS - 1 SP - 3 EP - 15 ER - TY - CHAP A1 - Meer, Klaus A1 - Ziegler, Martin ED - Kučera, Luděk T1 - Real Computational Universality: The word problem for a class of groups with infinite presentation T2 - Mathematical foundations of computer science 2007, 32nd international symposium, MFCS 2007, Český Krumlov, Czech Republic, August 26-31, 2007, proceedings Y1 - 2007 SN - 978-3-540-74455-9 SP - 726 EP - 737 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Ziegler, Martin ED - Beckmann, Arnold T1 - Uncomputability below the real halting problem T2 - Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings. Y1 - 2006 SN - 978-3-540-35466-6 SP - 368 EP - 377 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus ED - Beckmann, Arnold T1 - Optimization and approximation problems related to polynominal system solving T2 - Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings Y1 - 2006 SN - 978-3-540-35466-6 SP - 360 EP - 367 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus T1 - On the approximation of interval functions Y1 - 2006 ER - TY - CHAP A1 - Flarup Hansen, Uffe A1 - Meer, Klaus ED - Jedrzejowicz, Joanna T1 - Two logical hierarchies of optimization problems over the real numbers T2 - Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005 Y1 - 2005 SN - 978-3-540-29702-5 SP - 459 EP - 470 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus A1 - Ziegler, Martin ED - Liskiewicz, Maciej T1 - An explicit solution to Post's problem over the reals T2 - Fundamentals of computation theory, 15th international symposium, FCT 2005, Lübeck, Germany, August 17 - 20, 2005 Y1 - 2005 SN - 3-540-28193-2 SP - 456 EP - 467 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus ED - Cooper, Stuart Barry T1 - On some relations between approximation and PCPs over the real numbers T2 - New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005 Y1 - 2005 SN - 3-540-26179-6 SP - 322 EP - 331 PB - Springer CY - Heidelberg [u.a.] ER - TY - CHAP A1 - Malajovich, Gregorio A1 - Meer, Klaus T1 - Computing Minimal Multi-Homogeneous Bézout Numbers Is Hard Y1 - 2005 ER - TY - CHAP A1 - Meer, Klaus T1 - Transparent long proofs: A first PCP theorem for NP(R) T2 - Extended Abstract in 31st International Colloquium on Automata, Languages and Programming ICALP 2004, Turku Y1 - 2004 SN - 3-540-22849-7 SP - 959 EP - 970 PB - Springer CY - Berlin ER - TY - BOOK A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus A1 - Triesch, Eberhard T1 - Optimization Theory Y1 - 2004 SN - 978-1-402-08098-2 PB - Kluwer CY - Boston ER - TY - GEN A1 - Meer, Klaus T1 - Simulated Annealing versus Metropolis for a TSP instance T2 - Information Processing Letters Y1 - 2007 SN - 0020-0190 VL - 104 IS - 6 SP - 216 EP - 219 ER - TY - GEN A1 - Malajovich, Gregorio A1 - Meer, Klaus T1 - Computing Minimal Multi-Homogeneous Bézout Numbers Is Hard T2 - Theory of Computing Systems Y1 - 2007 SN - 1432-4350 VL - 40 IS - 4 SP - 553 EP - 570 ER - TY - GEN A1 - Meer, Klaus T1 - On some relations between approximation and PCPs over the real numbers T2 - Theory of Computing Systems Y1 - 2007 SN - 1432-4350 VL - 41 IS - 1 SP - 107 EP - 118 ER - TY - GEN A1 - Flarup Hansen, Uffe A1 - Meer, Klaus T1 - Two logical hierarchies of optimization problems over the real numbers T2 - Mathematical Logic Quaterly Y1 - 2006 SN - 0942-5616 VL - 52 IS - 1 SP - 37 EP - 50 ER - TY - GEN A1 - Meer, Klaus T1 - Transparent long proofs: A first PCP Theorem for NP(R) T2 - Foundations of Computational Mathematics Y1 - 2005 SN - 1615-3375 VL - 5 IS - 3 SP - 231 EP - 255 ER - TY - GEN A1 - Meer, Klaus T1 - Probabilistically checkable proofs over the reals T2 - Electronic notes in theoretical computer science : ENTCS Y1 - 2005 SN - 1571-0661 VL - 123 SP - 165 EP - 177 ER - TY - GEN A1 - Meer, Klaus T1 - On a refined analysis of some problems in interval arithmetic using real number complexity theory T2 - Reliable Computing Y1 - 2004 SN - 1385-3139 VL - 10 IS - 3 SP - 209 EP - 225 ER - TY - CHAP A1 - Gori, Marco A1 - Meer, Klaus ED - Cooper, Stuart Barry T1 - Some aspects of a complexity theory for continuous time systems T2 - Extended abstract, Proceedings Computability in Europe, CiE 2007, Siena, Italy, June 18 - 23, 2007 Y1 - 2007 SN - 978-3-540-73000-2 SP - 554 EP - 565 PB - Springer CY - Berlin ER - TY - CHAP A1 - Meer, Klaus A1 - Rautenbach, Dieter ED - Bodlaender, Hans L. T1 - On the OBDD size for graphs of bounded tree- and clique-width T2 - Parameterized and exact computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13 - 15, 2006 Y1 - 2006 SN - 978-3-540-39098-5 SP - 72 EP - 83 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Flarup Hansen, Uffe A1 - Meer, Klaus ED - Calude, Cristian T1 - Approximation classes for real number optimization problems T2 - Extended abstract, 5th International conference on Unconventional Computation, York, UK, September 4-8, 2006 Y1 - 2006 SN - 978-3-540-38593-6 SP - 86 EP - 100 PB - Springer CY - Berlin ER - TY - CHAP A1 - Zheng, Xizhong ED - Brattka, Vasco T1 - A Computability Theory of Real Numbers T2 - CCA 2008, August 21 - 24, 2008, Hagen, Germany Y1 - 2008 PB - Hagen CY - Fernuniv. ER - TY - CHAP A1 - Meer, Klaus ED - Ambos-Spies, Klaus T1 - On Ladner's Result for a Class of Real Machines with Restricted use of Constants T2 - 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19 - 24, 2009 Y1 - 2009 SN - 978-3-642-03072-7 SP - 352 EP - 361 PB - Springer CY - Heidelber [u.a.] ER - TY - CHAP A1 - Rettinger, Robert A1 - Zheng, Xizhong T1 - Points on Computable Curves of Computable Lengths Y1 - 2009 ER - TY - CHAP A1 - Rettinger, Robert A1 - Zheng, Xizhong T1 - On the Computability of the Rectifiable Simple Curves Y1 - 2009 ER - TY - GEN A1 - Meer, Klaus T1 - Fragestellungen aus Mathematik und theoretischer Informatik bei der Konstruktion von Getrieben T2 - Forum der Forschung Y1 - 2008 SN - 0947-6989 VL - 12 IS - 21 SP - 145 EP - 150 ER - TY - JOUR A1 - Zheng, Xizhong T1 - Classification of Computably Approximable Real Numbers Y1 - 2008 ER - TY - JOUR A1 - Zheng, Xizhong T1 - A Hierarchy of Computably Enumerable Reals Y1 - 2008 ER - TY - GEN A1 - Meer, Klaus A1 - Ziegler, Martin T1 - Real Computational Universality: The word problem for a class of groups with infinite presentation Y1 - 2009 ER - TY - CHAP A1 - Koiran, Pascal A1 - Meer, Klaus T1 - On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width T2 - Graph-theoretic concepts in computer science, 34th international workshop, WG 2008, Durham, UK, June 30-July 2, 2008 Y1 - 2008 SN - 978-3-540-92247-6 SP - 252 EP - 263 PB - Springer CY - Berlin [u.a.] ER - TY - GEN A1 - Koiran, Pascal A1 - Meer, Klaus A1 - Briquel, Irénée T1 - On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width Y1 - 2011 ER - TY - GEN A1 - Meer, Klaus T1 - Treewidth in Algebraic Complexity Y1 - 2010 ER - TY - CHAP A1 - Meer, Klaus T1 - An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents Y1 - 2011 ER - TY - CHAP A1 - Noack, Andreas A1 - Rotta, Randolf T1 - Multi-level Algorithms for Modularity Clustering N2 - Modularity is a widely used quality measure for graph clusterings. Its exact maximization is prohibitively expensive for large graphs. Popular heuristics progressively merge clusters starting from singletons (coarsening), and optionally improve the resulting clustering by moving vertices between clusters (refinement). This paper experimentally compares existing and new heuristics of this type with respect to their effectiveness (achieved modularity) and runtime. For coarsening, it turns out that the most widely used criterion for merging clusters (modularity increase) is outperformed by other simple criteria, and that a recent multi-step algorithm is no improvement over simple single-step coarsening for these criteria. For refinement, a new multi-level algorithm produces significantly better clusterings than conventional single-level algorithms. A comparison with published benchmark results and algorithm implementations shows that combinations of coarsening and multi-level refinement are competitive with the best algorithms in the literature. KW - Clustering KW - Algorithmen Y1 - 2009 UR - http://www.springerlink.com/content/qugv7708h3806230/ ER - TY - CHAP A1 - Meer, Klaus T1 - Almost transparent short proof for NP? T2 - Extended abstract, Proceedings 18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, 2011 Y1 - 2011 SN - 978-3-642-22952-7 SP - 41 EP - 52 ER - TY - GEN A1 - Rotta, Randolf A1 - Noack, Andreas T1 - Multilevel local search algorithms for modularity clusterin T2 - Journal on Experimental Algorithmics Y1 - 2011 SN - 1084-6654 VL - 16 IS - 2 ER - TY - GEN A1 - Meer, Klaus T1 - On Ladnerʼs result for a class of real machines with restricted use of constants T2 - Information and Computation Y1 - 2012 UR - http://www.sciencedirect.com/science/article/pii/S0890540111001507# SN - 0890-5401 VL - 210 SP - 13 EP - 20 ER - TY - GEN A1 - Rotta, Randolf A1 - Prescher, Thomas A1 - Traue, Jana A1 - Nolte, Jörg T1 - Data Sharing Mechanisms for Parallel Graph Algorithms on the Intel SCC T2 - MARC Symposium at ONERA'2012, July 19th–20th 2012, Toulouse, Frankreich Y1 - 2012 UR - http://hal.archives-ouvertes.fr/hal-00718993 SN - 978-2-7257-0016-8 N1 - Best Paper Award 2012 SP - 13 EP - 18 ER - TY - GEN A1 - Baartse, Martijn A1 - Barmpalias, George T1 - On the gap between trivial and nontrivial initial segment prefix-free complexity T2 - Theory of Computing Systems N2 - An infinite sequence X is said to have trivial (prefix-free) initial segment complexity if the prefix-free Kolmogorov complexity of each initial segment of X is the same as the complexity of the sequence of 0s of the same length, up to a constant. We study the gap between the minimum complexity K(0 n ) and the initial segment complexity of a nontrivial sequence, and in particular the nondecreasing unbounded functions f such that (⋆) for a nontrivial sequence X, where K denotes the prefix-free complexity. Our first result is that there exists a $\varDelta^{0}_{3}$ unbounded nondecreasing function f which does not have this property. It is known that such functions cannot be $\varDelta^{0}_{2}$ hence this is an optimal bound on their arithmetical complexity. Moreover it improves the bound $\varDelta^{0}_{4}$ that was known from Csima and Montalbán (Proc. Amer. Math. Soc. 134(5):1499–1502, 2006). Our second result is that if f is $\varDelta^{0}_{2}$ then there exists a non-empty $\varPi^{0}_{1}$ class of reals X with nontrivial prefix-free complexity which satisfy (⋆). This implies that in this case there uncountably many nontrivial reals X satisfying (⋆) in various well known classes from computability theory and algorithmic randomness; for example low for Ω, non-low for Ω and computably dominated reals. A special case of this result was independently obtained by Bienvenu, Merkle and Nies (STACS, pp. 452–463, 2011). KW - Kolmogorov complexity – Initial segment prefix-free complexity – K-triviality – Low for Ω Y1 - 2012 UR - http://www.springerlink.com/content/h0k3581g7202p574/ SN - 1433-0490 ER - TY - GEN A1 - Rotta, Randolf A1 - Büchner, Steffen A1 - Nolte, Jörg T1 - Middleware for Many-Cores - Why It Is Needed and What Functionality It Should Provide T2 - 4th USENIX Workshop on Hot Topics in Parallelism (HotPar '12), Berkeley, 2012 N2 - Today's multi-cores and future many-cores are NUMA architectures with complex cache hierarchies and multiple memory channels. Depending on the topologies of these memory networks we find everything from true data sharing with shared caches to distributed memory architectures which just pretend to be physical shared memory systems. In fact, most many-cores are hybrid systems that exhibit the characteristics of both distributed systems and SMPs. In this paper we argue in favor of middleware platforms for many-cores. We will discuss the needed functionality in contrast to common distributed system middleware and present micro benchmarks on several architectures to substantiate our claims. Y1 - 2012 UR - https://www.usenix.org/conference/hotpar12/tech-schedule/poster-session ER - TY - GEN A1 - Rotta, Randolf A1 - Prescher, Thomas A1 - Traue, Jana A1 - Nolte, Jörg T1 - In-Memory Communication Mechanisms for Many-Cores – Experiences with the Intel SCC T2 - TACC-Intel Highly Parallel Computing Symposium (TIHPCS), Austin/Texas, 2012 N2 - Many-core processors combine fast on-chip communication with access to large amounts of shared memory. This makes it possible to exploit the benefits of distributed as well as shared memory programming models within single parallel algorithms. While large amounts of data can be shared in the memory and caches, coordinating the activities of hundreds of cores relies on cross core communication mechanisms with ultra low latency for very small messages. In this paper we discuss two communication protocols for the Intel SCC and compare them to the MPI implementation of the SCC. Our micro-benchmark results underline that special purpose protocols for small messages make much finer levels of parallelism possible than general purpose message passing systems. Index Terms—many-core, message passing, shared memory Y1 - 2012 UR - http://www.tacc.utexas.edu/documents/13601/4234acca-2171-4465-aa48-7592d5e577f9 UR - http://www.tacc.utexas.edu/documents/13601/06d702ab-3f48-4942-9b07-2fbd880d4310 UR - http://www.tacc.utexas.edu/ti-hpcs12 ER - TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn T1 - The PCP theorem for NP over the reals T2 - 30th Symposium on Theoretical Aspects of Computer Science STACS , Kiel, 2013 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-39262 UR - http://drops.dagstuhl.de/opus/volltexte/2013/3926/ SP - 104 EP - 115 CY - Leibnitz ER - TY - GEN A1 - Meer, Klaus T1 - Some initial thoughts on bounded query computations over the reals T2 - International Journal of Foundations of Computer Science Y1 - 2012 U6 - https://doi.org/10.1142/S0129054112400618 SN - 0129-0541 N1 - Special Issue on 'Frontier between Decidability and Undecidability and Related Problem' VL - 23 IS - 7 SP - 1499 EP - 1510 ER - TY - CHAP A1 - Meer, Klaus T1 - On the complexity of some problems in interval arithmetic T2 - Proceedings, 28th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 2003 Y1 - 2003 SN - 3-540-40671-9 SP - 582 EP - 591 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus ED - Walz, Guido T1 - Das Simplexverfahren T2 - Lexikon der Mathematik, Band 5 Y1 - 2002 SN - 3-8274-0437-1 SP - 27 EP - 30 PB - Spektrum Akademischer Verlag CY - Heidelberg ER - TY - CHAP A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus ED - Walz, Guido T1 - Ellipsoidmethoden T2 - Lexikon der Mathematik, Band 2 Y1 - 2001 SN - 3-8274-0434-7 SP - 37 EP - 38 PB - Spektrum Akademischer Verlag CY - Heidelberg ER - TY - CHAP A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus ED - Walz, Guido T1 - Innere-Punkte Methoden T2 - Lexikon der Mathematik, Band 2 Y1 - 2001 SN - 3-8274-0434-7 SP - 491 EP - 494 PB - Spektrum Akademischer Verlag CY - Heidelberg ER - TY - GEN A1 - Meer, Klaus T1 - An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents T2 - Theory of Computing Systems Y1 - 2014 SN - 1432-4350 VL - 55 IS - 2 SP - 330 EP - 346 ER - TY - CHAP A1 - Lickteig, Thomas A1 - Meer, Klaus A1 - Pardo, Luis Miguel T1 - Real Computation and Complexity, Dagstuhl seminar Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-4994 UR - http://drops.dagstuhl.de/opus/volltexte/2006/499/ PB - Internationale Begegnungs- und Forschungszentrum für Informatik CY - Dagstuhl ER - TY - CHAP A1 - Jongen, Hubertus Theodor A1 - Meer, Klaus ED - Walz, Guido T1 - Optimierung T2 - Faszination Mathematik Y1 - 2003 SN - 3-8274-1419-9 SP - 211 EP - 216 PB - Spektrum Akademischer Verlag CY - Heidelberg ER - TY - JOUR A1 - Meer, Klaus T1 - Syropoulos, Apostolos: Hypercomputation. Berlin : Springer, 2008 JF - AMS Mathematical Reviews Y1 - 2009 SN - 0025-5629 IS - 2009j ER - TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn ED - Montaña, José Luis ED - Pardo, Luis Miguel T1 - Topics in Real and Complex Number Complexity Theory T2 - Recent Advances in Real Complexity and Computation Y1 - 2013 UR - http://bookstore.ams.org/conm-604?c=1 SN - 978-0-8218-9150-6 U6 - https://doi.org/10.1090/conm/604 SP - 1 EP - 53 PB - American Mathematical Society CY - Providence, RI ER - TY - GEN A1 - Meer, Klaus A1 - Schmitt, Burkhard A1 - Schreiber, Harold T1 - Dimensional Synthesis of Planar Stephenson-Mechanisms for Motion Generation by Circlepoint Search and Homotopy Methods T2 - Mechanism and Machine Theory N2 - The kinematic synthesis of Stephenson mechanisms for motion generation is often based on specifying arbitrary values for certain kinematic dimensions. If no appropriate values are known, an inadequate choice can make it impossible to find a good mechanism. In the present paper a synthesis method is described where kinematic dimensions can be chosen a priori (to meet side conditions, e.g., a limited area for the locations of the fixed pivots), but do not have to be chosen. A circlepoint search in combination with homotopy methods will be applied. Concerning the homotopy methods two approaches – via the Bézout number and the BKK bound – will be compared. Y1 - 2002 UR - http://www.sciencedirect.com/science/article/pii/S0094114X02000162 U6 - https://doi.org/10.1016/S0094-114X(02)00016-2 SN - 0094-114X VL - 37 IS - 7 SP - 717 EP - 737 ER - TY - GEN A1 - Meer, Klaus A1 - Weber, Gerhard Wilhelm T1 - Some aspects of studying an optimization or decision problem in different computational models T2 - European Journal of Operational Research N2 - In this paper we want to discuss some of the features coming up when analyzing a problem in different complexity theoretic frameworks. The focus will be on two problems. The first is related to mathematical optimization. We consider the quadratic programming problem of minimizing a quadratic polynomial on a polyhedron. We discuss how the complexity of this problem might change if we consider real data together with an algebraic model of computation (the Blum–Shub–Smale model) instead of rational inputs together with the Turing machine model. The results obtained will lead us to the second problem; it deals with the intrinsic structure of complexity classes in models over real- or algebraically closed fields. A classical theorem by Ladner for the Turing model is examined in these different frameworks. Both examples serve well for working out in how far different approaches to the same problem might shed light upon each other. In some cases this will lead to quite diverse results with respect to the different models. On the other hand, for some problems the more general approach can also give a unifying idea why results hold true in several frameworks. The paper is of tutorial character in that it collects some results into the above direction obtained previously. KW - Complexity theory Saturation KW - Algebraic models of computation KW - Linear and quadratic programming KW - Structure of complexity classes Y1 - 2002 UR - http://www.sciencedirect.com/science/article/pii/S0377221702002692 U6 - https://doi.org/10.1016/S0377-2217(02)00269-2 SN - 0377-2217 VL - 143 IS - 2 SP - 406 EP - 418 ER - TY - JOUR A1 - Meer, Klaus T1 - Wegener, Ingo: Komplexitätstheorie. Berlin : Springer, 2003 JF - Jahresbericht der Deutschen Mathematiker-Vereinigung Y1 - 2006 SN - 0012-0456 VL - 108 IS - 2 SP - 5 EP - 8 ER - TY - JOUR A1 - Meer, Klaus T1 - Blum, Lenore [u.a.]: Complexity and real computation. Berlin : Springer, 1998 JF - AMS Mathematical Reviews Y1 - 1999 SN - 0025-5629 IS - 99a SP - 509 EP - 600 ER - TY - GEN ED - Beckmann, Arnold ED - Csuhaj-Varjú, Erzsébet ED - Meer, Klaus T1 - Language, Life, Limits 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014, Proceedings N2 - This book constitutes the refereed proceedings of the 10th Conference on Computability in Europe, CiE 2014, held in Budapest, Hungary, in June 2014. The 42 revised papers presented were carefully reviewed and selected from 78 submissions and included together with 15 invited papers in this proceedings. The conference had six special sessions: computational linguistics, bio-inspired computation, history and philosophy of computing, computability theory, online algorithms and complexity in automata theory. Y1 - 2014 SN - 978-3-319-08018-5 U6 - https://doi.org/10.1007/978-3-319-08019-2 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - GEN A1 - Meer, Klaus A1 - Naif, Ameen T1 - Generalized finite automata over real and complex numbers T2 - Theoretical Computer Science N2 - In a recent work, Gandhi, Khoussainov, and Liu [7] introduced and studied a generalized model of finite automata able to work over arbitrary structures. As one relevant area of research for this model the authors identify studying such automata over particular structures such as real and algebraically closed fields. In this paper we start investigations into this direction. We prove several structural results about sets accepted by such automata, and analyze decidability as well as complexity of several classical questions about automata in the new framework. Our results show quite a diverse picture when compared to the well known results for finite automata over finite alphabets. KW - Generalized finite automata KW - Real and complex number computations KW - Decision problems for automata over uncountable structures Y1 - 2015 UR - http://www.sciencedirect.com/science/article/pii/S0304397515003928 U6 - https://doi.org/10.1016/j.tcs.2015.05.001 SN - 0304-3975 VL - Vol. 591 SP - 85 EP - 98 ER - TY - GEN A1 - Meer, Klaus A1 - Baartse, Martijn T1 - The PCP theorem for NP over the reals T2 - Foundations of Computational Mathematics KW - Probabilistically checkable proofs Real and complex number computations PCP theorem Hilbert Nullstellensatz decision problem Y1 - 2015 UR - http://link.springer.com/article/10.1007/s10208-014-9188-x?sa_campaign=email/event/articleAuthor/onlineFirst U6 - https://doi.org/10.1007/s10208-014-9188-x SN - 1615-3375 VL - 15 IS - 3 SP - 651 EP - 680 ER -