@misc{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {Interactive proofs and a Shamir-like result for real number computations}, series = {Computational Complexity}, journal = {Computational Complexity}, issn = {1016-3328}, doi = {10.1007/s00037-018-0174-6}, pages = {33}, language = {en} } @misc{OPUS4-22626, title = {Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018}, editor = {Brandst{\"a}dt, Andreas and K{\"o}hler, Ekkehard and Meer, Klaus}, publisher = {Springer International Publishing}, address = {Cham, Switzerland}, isbn = {978-3-030-00255-8}, pages = {XIII, 384}, language = {en} } @misc{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {An algebraic proof of the real number PCP theorem}, series = {Journal of Complexity}, volume = {40}, journal = {Journal of Complexity}, issn = {0885-064X}, doi = {10.1016/j.jco.2016.11.006}, pages = {34 -- 77}, abstract = {The PCP theorem has recently been shown to hold as well in the real number model of Blum, Shub, and Smale (Baartse and Meer, 2015). The proof given there structurally closely follows the proof of the original PCP theorem by Dinur (2007). In this paper we show that the theorem also can be derived using algebraic techniques similar to those employed by Arora et al. (Arora et al., 1998; Arora and Safra, 1998) in the first proof of the PCP theorem. This needs considerable additional efforts. Due to severe problems when using low degree algebraic polynomials over the reals as codewords for one of the verifiers to be constructed, we work with certain trigonometric polynomials. This entails the necessity to design new segmentation procedures in order to obtain well structured real verifiers appropriate for applying the classical technique of verifier composition. We believe that designing as well an algebraic proof for the real PCP theorem on one side leads to interesting questions in real number complexity theory and on the other sheds light on which ingredients are necessary in order to prove an important result as the PCP theorem in different computational models.}, language = {en} } @periodical{OPUS4-21276, title = {Mathematical Logic Quarterly}, volume = {Vol. 63}, number = {1-2, 3-4, 5, 6}, editor = {Meer, Klaus and L{\"o}we, Benedikt and Macpherson, H. Dugald}, publisher = {Wiley-VCH}, address = {Berlin [u.a.]}, issn = {1521-3870}, language = {en} } @periodical{OPUS4-21279, title = {Journal of Complexity}, volume = {Vol. 38 - 43}, editor = {Meer, Klaus and Novak, Erich and Dick, Josef and Hinrichs, Aicke and Ritter, Klaus and Sloan, Ian and Wasilkowski, Greg and Wozniakowski, Henryk}, publisher = {Elsevier}, address = {Amsterdam [u.a.]}, issn = {0885-064X}, language = {en} } @inproceedings{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {Real Interactive Proofs for VPSPACE}, series = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik GmbH}, address = {Wadern}, isbn = {978-3-95977-016-3}, doi = {10.4230/LIPIcs.MFCS.2016.14}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-64300}, pages = {14.1 -- 14.13}, language = {en} } @inproceedings{MeerNaif, author = {Meer, Klaus and Naif, Ameen}, title = {Periodic Generalized Automata over the Reals}, series = {Language and Automata Theory and Applications 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings}, booktitle = {Language and Automata Theory and Applications 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings}, editor = {Dediu, Adrian-Horia and Janoušek, Jan and Mart{\´i}n-Vide, Carlos and Truthe, Bianca}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-29999-0}, doi = {10.1007/978-3-319-30000-9}, pages = {168 -- 180}, language = {en} } @periodical{OPUS4-21283, title = {Journal of Complexity}, volume = {Vol. 32 - 37}, editor = {Meer, Klaus and Novak, Erich and Dick, Josef and Hinrichs, Aicke and Ritter, Klaus and Sloan, Ian and Wasilkowski, Greg and Wozniakowski, Henryk}, publisher = {Elsevier}, address = {Amsterdam [u.a.]}, issn = {0885-064X}, language = {en} } @periodical{OPUS4-21277, title = {Mathematical Logic Quarterly}, volume = {Vol. 62}, number = {1-2, 3, 4-5, 6}, editor = {Meer, Klaus and L{\"o}we, Benedikt and Macpherson, H. Dugald}, publisher = {Wiley-VCH}, address = {Berlin [u.a.]}, issn = {1521-3870}, language = {en} } @misc{OPUS4-15563, title = {Informatik 2015, 45. Jahrestagung der Gesellschaft f{\"u}r Informatik,Informatik, Energie und Umwelt, Tagung von 28. September - 2. Oktober 2015 in Cottbus}, editor = {Cunningham, Douglas W. and Hofstedt, Petra and Meer, Klaus and Schmitt, Ingo}, publisher = {Gesellschaft f{\"u}r Informatik}, address = {Bonn}, isbn = {978-3-88579-640-4}, language = {de} } @misc{MeerNaif, author = {Meer, Klaus and Naif, Ameen}, title = {Generalized finite automata over real and complex numbers}, series = {Theoretical Computer Science}, volume = {Vol. 591}, journal = {Theoretical Computer Science}, issn = {0304-3975}, doi = {10.1016/j.tcs.2015.05.001}, pages = {85 -- 98}, abstract = {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.}, language = {en} } @misc{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {The PCP theorem for NP over the reals}, series = {Foundations of Computational Mathematics}, volume = {15}, journal = {Foundations of Computational Mathematics}, number = {3}, issn = {1615-3375}, doi = {10.1007/s10208-014-9188-x}, pages = {651 -- 680}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {Some results on interactive proofs for real computations}, series = {Evolving Computability 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015, Proceedings}, booktitle = {Evolving Computability 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015, Proceedings}, editor = {Beckmann, Arnold and Mitrana, Victor and Soskova, Mariya}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-20027-9}, doi = {10.1007/978-3-319-20028-6}, pages = {107 -- 116}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {An algebraic proof of the real number PCP theorem}, series = {Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II}, booktitle = {Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II}, publisher = {Springer-Verlag}, address = {Berlin [u.a.]}, isbn = {978-3-662-48053-3}, doi = {10.1007/978-3-662-48054-0}, pages = {50 -- 61}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents}, series = {Theory of Computing Systems}, volume = {55}, journal = {Theory of Computing Systems}, number = {2}, issn = {1432-4350}, pages = {330 -- 346}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {Testing Low Degree Trigonometric Polynomials}, series = {Computer Science - Theory and Applications 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014, Proceedings}, booktitle = {Computer Science - Theory and Applications 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014, Proceedings}, editor = {Hirsch, Edward and Kuznetsov, Sergei O. and Pin, Jean-{\´E}ric and Vereshchagin, Nikolay}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-06685-1}, doi = {10.1007/978-3-319-06686-8}, pages = {77 -- 96}, language = {en} } @inproceedings{MeerNaif, author = {Meer, Klaus and Naif, Ameen}, title = {Generalized Finite Automata over Real and Complex Numbers}, series = {Theory and Applications of Models of Computation 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014, Proceedings}, booktitle = {Theory and Applications of Models of Computation 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014, Proceedings}, editor = {Gopal, T. V. and Agrawal, Manindra and Li, Angsheng and Cooper, Stuart Barry}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-06088-0}, doi = {10.1007/978-3-319-06089-7}, pages = {168 -- 187}, language = {en} } @misc{OPUS4-15615, title = {Language, Life, Limits 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014, Proceedings}, editor = {Beckmann, Arnold and Csuhaj-Varj{\´u}, Erzs{\´e}bet and Meer, Klaus}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-08018-5}, doi = {10.1007/978-3-319-08019-2}, pages = {XIV, 410}, abstract = {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.}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {Topics in Real and Complex Number Complexity Theory}, series = {Recent Advances in Real Complexity and Computation}, booktitle = {Recent Advances in Real Complexity and Computation}, editor = {Monta{\~n}a, Jos{\´e} Luis and Pardo, Luis Miguel}, publisher = {American Mathematical Society}, address = {Providence, RI}, isbn = {978-0-8218-9150-6}, doi = {10.1090/conm/604}, pages = {1 -- 53}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {The PCP theorem for NP over the reals}, series = {30th Symposium on Theoretical Aspects of Computer Science STACS , Kiel, 2013}, booktitle = {30th Symposium on Theoretical Aspects of Computer Science STACS , Kiel, 2013}, address = {Leibnitz}, doi = {10.4230/LIPIcs.STACS.2013.104}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-39262}, pages = {104 -- 115}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On Ladnerʼs result for a class of real machines with restricted use of constants}, series = {Information and Computation}, volume = {210}, journal = {Information and Computation}, issn = {0890-5401}, pages = {13 -- 20}, language = {en} } @misc{RottaPrescherTraueetal., author = {Rotta, Randolf and Prescher, Thomas and Traue, Jana and Nolte, J{\"o}rg}, title = {Data Sharing Mechanisms for Parallel Graph Algorithms on the Intel SCC}, series = {MARC Symposium at ONERA'2012, July 19th-20th 2012, Toulouse, Frankreich}, journal = {MARC Symposium at ONERA'2012, July 19th-20th 2012, Toulouse, Frankreich}, isbn = {978-2-7257-0016-8}, pages = {13 -- 18}, language = {en} } @misc{BaartseBarmpalias, author = {Baartse, Martijn and Barmpalias, George}, title = {On the gap between trivial and nontrivial initial segment prefix-free complexity}, series = {Theory of Computing Systems}, journal = {Theory of Computing Systems}, issn = {1433-0490}, pages = {20}, abstract = {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{\´a}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).}, language = {en} } @misc{RottaPrescherTraueetal., author = {Rotta, Randolf and Prescher, Thomas and Traue, Jana and Nolte, J{\"o}rg}, title = {In-Memory Communication Mechanisms for Many-Cores - Experiences with the Intel SCC}, series = {TACC-Intel Highly Parallel Computing Symposium (TIHPCS), Austin/Texas, 2012}, journal = {TACC-Intel Highly Parallel Computing Symposium (TIHPCS), Austin/Texas, 2012}, abstract = {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}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Some initial thoughts on bounded query computations over the reals}, series = {International Journal of Foundations of Computer Science}, volume = {23}, journal = {International Journal of Foundations of Computer Science}, number = {7}, issn = {0129-0541}, doi = {10.1142/S0129054112400618}, pages = {1499 -- 1510}, language = {en} } @misc{RottaBuechnerNolte, author = {Rotta, Randolf and B{\"u}chner, Steffen and Nolte, J{\"o}rg}, title = {Middleware for Many-Cores - Why It Is Needed and What Functionality It Should Provide}, series = {4th USENIX Workshop on Hot Topics in Parallelism (HotPar '12), Berkeley, 2012}, journal = {4th USENIX Workshop on Hot Topics in Parallelism (HotPar '12), Berkeley, 2012}, abstract = {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.}, language = {en} } @misc{KoiranMeerBriquel, author = {Koiran, Pascal and Meer, Klaus and Briquel, Ir{\´e}n{\´e}e}, title = {On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width}, language = {en} } @misc{RottaNoack, author = {Rotta, Randolf and Noack, Andreas}, title = {Multilevel local search algorithms for modularity clusterin}, series = {Journal on Experimental Algorithmics}, volume = {16}, journal = {Journal on Experimental Algorithmics}, number = {2}, issn = {1084-6654}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {Almost transparent short proof for NP?}, series = {Extended abstract, Proceedings 18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, 2011}, booktitle = {Extended abstract, Proceedings 18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, 2011}, isbn = {978-3-642-22952-7}, pages = {41 -- 52}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Treewidth in Algebraic Complexity}, language = {en} } @misc{MeerRautenbach, author = {Meer, Klaus and Rautenbach, Dieter}, title = {On the OBDD size for graphs of bounded tree- and clique-width}, language = {en} } @inproceedings{NoackRotta, author = {Noack, Andreas and Rotta, Randolf}, title = {Multi-level Algorithms for Modularity Clustering}, abstract = {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.}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On Ladner's Result for a Class of Real Machines with Restricted use of Constants}, series = {5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19 - 24, 2009}, booktitle = {5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19 - 24, 2009}, editor = {Ambos-Spies, Klaus}, publisher = {Springer}, address = {Heidelber [u.a.]}, isbn = {978-3-642-03072-7}, pages = {352 -- 361}, language = {en} } @inproceedings{RettingerZheng, author = {Rettinger, Robert and Zheng, Xizhong}, title = {Points on Computable Curves of Computable Lengths}, language = {en} } @inproceedings{RettingerZheng, author = {Rettinger, Robert and Zheng, Xizhong}, title = {On the Computability of the Rectifiable Simple Curves}, language = {en} } @misc{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {Real Computational Universality: The word problem for a class of groups with infinite presentation}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Syropoulos, Apostolos: Hypercomputation. Berlin : Springer, 2008}, series = {AMS Mathematical Reviews}, journal = {AMS Mathematical Reviews}, number = {2009j}, issn = {0025-5629}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Complexity aspects of a semi-infinite optimization problem}, series = {Optimization : a Journal of Mathematical Programming and Operations Research}, volume = {57}, journal = {Optimization : a Journal of Mathematical Programming and Operations Research}, number = {1}, issn = {1029-4945}, pages = {143 -- 152}, language = {en} } @misc{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {An explicit solution to Post's problem over the reals}, series = {Journal of Complexity}, volume = {24}, journal = {Journal of Complexity}, number = {1}, issn = {0885-064x}, pages = {3 -- 15}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Fragestellungen aus Mathematik und theoretischer Informatik bei der Konstruktion von Getrieben}, series = {Forum der Forschung}, volume = {12}, journal = {Forum der Forschung}, number = {21}, issn = {0947-6989}, pages = {145 -- 150}, language = {de} } @inproceedings{KoiranMeer, author = {Koiran, Pascal and Meer, Klaus}, title = {On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width}, series = {Graph-theoretic concepts in computer science, 34th international workshop, WG 2008, Durham, UK, June 30-July 2, 2008}, booktitle = {Graph-theoretic concepts in computer science, 34th international workshop, WG 2008, Durham, UK, June 30-July 2, 2008}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-92247-6}, pages = {252 -- 263}, language = {en} } @inproceedings{Zheng, author = {Zheng, Xizhong}, title = {A Computability Theory of Real Numbers}, series = {CCA 2008, August 21 - 24, 2008, Hagen, Germany}, booktitle = {CCA 2008, August 21 - 24, 2008, Hagen, Germany}, editor = {Brattka, Vasco}, publisher = {Hagen}, address = {Fernuniv.}, language = {en} } @article{Zheng, author = {Zheng, Xizhong}, title = {Classification of Computably Approximable Real Numbers}, language = {en} } @article{Zheng, author = {Zheng, Xizhong}, title = {A Hierarchy of Computably Enumerable Reals}, language = {en} } @incollection{Zheng, author = {Zheng, Xizhong}, title = {Bounded Computable Enumerability and Hierarchy of Computably Enumerable Reals}, language = {en} } @inproceedings{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {Real Computational Universality: The word problem for a class of groups with infinite presentation}, series = {Mathematical foundations of computer science 2007, 32nd international symposium, MFCS 2007, Česk{\´y} Krumlov, Czech Republic, August 26-31, 2007, proceedings}, booktitle = {Mathematical foundations of computer science 2007, 32nd international symposium, MFCS 2007, Česk{\´y} Krumlov, Czech Republic, August 26-31, 2007, proceedings}, editor = {Kučera, Luděk}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-74455-9}, pages = {726 -- 737}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Simulated Annealing versus Metropolis for a TSP instance}, series = {Information Processing Letters}, volume = {104}, journal = {Information Processing Letters}, number = {6}, issn = {0020-0190}, pages = {216 -- 219}, language = {en} } @misc{MalajovichMeer, author = {Malajovich, Gregorio and Meer, Klaus}, title = {Computing Minimal Multi-Homogeneous B{\´e}zout Numbers Is Hard}, series = {Theory of Computing Systems}, volume = {40}, journal = {Theory of Computing Systems}, number = {4}, issn = {1432-4350}, pages = {553 -- 570}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On some relations between approximation and PCPs over the real numbers}, series = {Theory of Computing Systems}, volume = {41}, journal = {Theory of Computing Systems}, number = {1}, issn = {1432-4350}, pages = {107 -- 118}, language = {en} } @inproceedings{GoriMeer, author = {Gori, Marco and Meer, Klaus}, title = {Some aspects of a complexity theory for continuous time systems}, series = {Extended abstract, Proceedings Computability in Europe, CiE 2007, Siena, Italy, June 18 - 23, 2007}, booktitle = {Extended abstract, Proceedings Computability in Europe, CiE 2007, Siena, Italy, June 18 - 23, 2007}, editor = {Cooper, Stuart Barry}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-73000-2}, pages = {554 -- 565}, language = {en} } @misc{ChenSuZheng, author = {Chen, Qingliang and Su, Kaile and Zheng, Xizhong}, title = {Primitive Recursiveness of Real Numbers under Different Representations}, series = {Electronic Notes in Theoretical Computer Science}, volume = {167}, journal = {Electronic Notes in Theoretical Computer Science}, issn = {1571-0661}, pages = {303 -- 324}, language = {en} } @misc{Zheng, author = {Zheng, Xizhong}, title = {Classification of the Computable Approximations}, series = {Electronic Notes in Theoretical Computer Science}, volume = {167}, journal = {Electronic Notes in Theoretical Computer Science}, issn = {1571-0661}, pages = {325 -- 344}, language = {en} } @article{Zheng, author = {Zheng, Xizhong}, title = {On the Hierarchies of Delta 0_2 real Numbers}, language = {en} } @article{ChenSuZheng, author = {Chen, Q. and Su, K. and Zheng, Xizhong}, title = {Primitive Recursive Real Numbers}, language = {en} } @phdthesis{Zheng, author = {Zheng, Xizhong}, title = {Effective Hierarchy of Real Numbers}, publisher = {Shaker}, address = {Aachen}, isbn = {978-3-8322-6343-0}, pages = {X, 244}, language = {en} } @misc{RettingerZheng, author = {Rettinger, Robert and Zheng, Xizhong}, title = {A hierarchy of Turing degrees of divergence bounded computable real numbers}, series = {Journal of Complexity}, volume = {22}, journal = {Journal of Complexity}, number = {6}, pages = {818 -- 826}, language = {en} } @inproceedings{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {Uncomputability below the real halting problem}, series = {Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings.}, booktitle = {Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings.}, editor = {Beckmann, Arnold}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-35466-6}, pages = {368 -- 377}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {Optimization and approximation problems related to polynominal system solving}, series = {Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings}, booktitle = {Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings}, editor = {Beckmann, Arnold}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-35466-6}, pages = {360 -- 367}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On the approximation of interval functions}, language = {en} } @inproceedings{MeerRautenbach, author = {Meer, Klaus and Rautenbach, Dieter}, title = {On the OBDD size for graphs of bounded tree- and clique-width}, series = {Parameterized and exact computation, Second International Workshop, IWPEC 2006, Z{\"u}rich, Switzerland, September 13 - 15, 2006}, booktitle = {Parameterized and exact computation, Second International Workshop, IWPEC 2006, Z{\"u}rich, Switzerland, September 13 - 15, 2006}, editor = {Bodlaender, Hans L.}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-39098-5}, pages = {72 -- 83}, language = {en} } @inproceedings{FlarupHansenMeer, author = {Flarup Hansen, Uffe and Meer, Klaus}, title = {Approximation classes for real number optimization problems}, series = {Extended abstract, 5th International conference on Unconventional Computation, York, UK, September 4-8, 2006}, booktitle = {Extended abstract, 5th International conference on Unconventional Computation, York, UK, September 4-8, 2006}, editor = {Calude, Cristian}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-38593-6}, pages = {86 -- 100}, language = {en} } @inproceedings{SuChenZhengetal., author = {Su, Kaile and Chen, Qingliang and Zheng, Xizhong and Yue, Weiya}, title = {Reasoning about Knowledge by SAT Solving}, series = {International Conference on Computational Intelligence and Security, CIS 2006, 3 - 6 Nov. 2006, Guangzhou, China}, booktitle = {International Conference on Computational Intelligence and Security, CIS 2006, 3 - 6 Nov. 2006, Guangzhou, China}, publisher = {IEEE Press}, address = {Piscataway, NJ}, isbn = {1-4244-0604-8}, pages = {536 -- 539}, language = {en} } @inproceedings{Zheng, author = {Zheng, Xizhong}, title = {A Computability Theory of Real Numbers}, series = {Logical approaches to computational barriers, second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings}, booktitle = {Logical approaches to computational barriers, second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 - July 5, 2006, proceedings}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-35466-2}, pages = {584 -- 594}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Wegener, Ingo: Komplexit{\"a}tstheorie. Berlin : Springer, 2003}, series = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, volume = {108}, journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, number = {2}, issn = {0012-0456}, pages = {5 -- 8}, language = {de} } @inproceedings{LickteigMeerPardo, author = {Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel}, title = {Real Computation and Complexity, Dagstuhl seminar}, publisher = {Internationale Begegnungs- und Forschungszentrum f{\"u}r Informatik}, address = {Dagstuhl}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-4994}, language = {en} } @misc{FlarupHansenMeer, author = {Flarup Hansen, Uffe and Meer, Klaus}, title = {Two logical hierarchies of optimization problems over the real numbers}, series = {Mathematical Logic Quaterly}, volume = {52}, journal = {Mathematical Logic Quaterly}, number = {1}, issn = {0942-5616}, pages = {37 -- 50}, language = {en} } @article{ChenSuYueetal., author = {Chen, Q. and Su, K. and Yue, W. and Zheng, Xizhong}, title = {Instantiation Space: A New Model for Security Protocol Logic}, language = {en} } @article{ChenRettingerSuetal., author = {Chen, Q. and Rettinger, Robert and Su, K. and Sattar, A. and Yue, W. and Lu, G. and Zheng, Xizhong}, title = {Verification of Authentication Protocols for Epistemic Goals via SAT Compilation}, language = {en} } @article{Zheng, author = {Zheng, Xizhong}, title = {Divergence bounded computable real numbers}, language = {en} } @inproceedings{RettingerZheng, author = {Rettinger, Robert and Zheng, Xizhong}, title = {On the Turing degrees of divergence bounded computable reals}, series = {New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005}, booktitle = {New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005}, editor = {Cooper, Stuart Barry}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-26179-6}, pages = {418 -- 428}, language = {en} } @inproceedings{RettingerZheng, author = {Rettinger, Robert and Zheng, Xizhong}, title = {Solovay reducibility on d-c.e. real numbers}, series = {Computing and combinatorics, 11th annual international conference, COCOON 2005, Kunming, China, August 16 - 29, 2005}, booktitle = {Computing and combinatorics, 11th annual international conference, COCOON 2005, Kunming, China, August 16 - 29, 2005}, editor = {Wang, Lusheng}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-28061-3}, pages = {359 -- 368}, language = {en} } @inproceedings{FlarupHansenMeer, author = {Flarup Hansen, Uffe and Meer, Klaus}, title = {Two logical hierarchies of optimization problems over the real numbers}, series = {Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005}, booktitle = {Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005}, editor = {Jedrzejowicz, Joanna}, publisher = {Springer}, address = {Berlin}, isbn = {978-3-540-29702-5}, pages = {459 -- 470}, language = {en} } @inproceedings{MeerZiegler, author = {Meer, Klaus and Ziegler, Martin}, title = {An explicit solution to Post's problem over the reals}, series = {Fundamentals of computation theory, 15th international symposium, FCT 2005, L{\"u}beck, Germany, August 17 - 20, 2005}, booktitle = {Fundamentals of computation theory, 15th international symposium, FCT 2005, L{\"u}beck, Germany, August 17 - 20, 2005}, editor = {Liskiewicz, Maciej}, publisher = {Springer}, address = {Berlin}, isbn = {3-540-28193-2}, pages = {456 -- 467}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On some relations between approximation and PCPs over the real numbers}, series = {New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005}, booktitle = {New computational paradigms, First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8 - 12, 2005}, editor = {Cooper, Stuart Barry}, publisher = {Springer}, address = {Heidelberg [u.a.]}, isbn = {3-540-26179-6}, pages = {322 -- 331}, language = {en} } @inproceedings{MalajovichMeer, author = {Malajovich, Gregorio and Meer, Klaus}, title = {Computing Minimal Multi-Homogeneous B{\´e}zout Numbers Is Hard}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Transparent long proofs: A first PCP Theorem for NP(R)}, series = {Foundations of Computational Mathematics}, volume = {5}, journal = {Foundations of Computational Mathematics}, number = {3}, issn = {1615-3375}, pages = {231 -- 255}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Probabilistically checkable proofs over the reals}, series = {Electronic notes in theoretical computer science : ENTCS}, volume = {123}, journal = {Electronic notes in theoretical computer science : ENTCS}, issn = {1571-0661}, pages = {165 -- 177}, language = {en} } @misc{ZhengRettinger, author = {Zheng, Xizhong and Rettinger, Robert}, title = {Effective Jordan decomposition}, series = {Theory of Computing System}, volume = {38}, journal = {Theory of Computing System}, number = {2}, issn = {1432-4350}, pages = {189 -- 209}, language = {en} } @article{Zheng, author = {Zheng, Xizhong}, title = {Closure properties of real numbers classes under CBV functions}, language = {en} } @article{ZhengRettingerBarmpalias, author = {Zheng, Xizhong and Rettinger, Robert and Barmpalias, George}, title = {h-Monotonically computable real numbers}, series = {Mathematical Logic Quarterly}, volume = {51}, journal = {Mathematical Logic Quarterly}, number = {2}, issn = {0942-5616}, pages = {157 -- 170}, language = {en} } @inproceedings{Zheng, author = {Zheng, Xizhong}, title = {On the hierarchy of Delta_02-numbers}, language = {en} } @inproceedings{ZhengRettinger, author = {Zheng, Xizhong and Rettinger, Robert}, title = {A note on the Turing degrees of divergence bounded computable reals}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On a refined analysis of some problems in interval arithmetic using real number complexity theory}, series = {Reliable Computing}, volume = {10}, journal = {Reliable Computing}, number = {3}, issn = {1385-3139}, pages = {209 -- 225}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On the Approximation of Interval Functions}, series = {Applied Parallel Computing. State of the Art in Scientific Computing, 7th International Workshop, PARA 2004, Lyngby, Denmark, June 20-23, 2004, Revised Selected Papers}, booktitle = {Applied Parallel Computing. State of the Art in Scientific Computing, 7th International Workshop, PARA 2004, Lyngby, Denmark, June 20-23, 2004, Revised Selected Papers}, editor = {Dongarra, Jack}, publisher = {Springer}, address = {Heidelberg [u.a.]}, isbn = {978-3-540-29067-4}, pages = {169 -- 178}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {Transparent long proofs: A first PCP theorem for NP(R)}, series = {Extended Abstract in 31st International Colloquium on Automata, Languages and Programming ICALP 2004, Turku}, booktitle = {Extended Abstract in 31st International Colloquium on Automata, Languages and Programming ICALP 2004, Turku}, publisher = {Springer}, address = {Berlin}, isbn = {3-540-22849-7}, pages = {959 -- 970}, language = {en} } @inproceedings{ZhengRettinger, author = {Zheng, Xizhong and Rettinger, Robert}, title = {On the extensions of Solovay Reducibility}, language = {en} } @misc{ZhengRettinger, author = {Zheng, Xizhong and Rettinger, Robert}, title = {Weak computability and representation of real numbers}, series = {Mathematical Logic Quarterly}, volume = {50}, journal = {Mathematical Logic Quarterly}, number = {4/5}, issn = {0942-5616}, pages = {431 -- 442}, language = {en} } @article{DowneyWuZheng, author = {Downey, Rod and Wu, D. and Zheng, Xizhong}, title = {Degrees of d.c.e. Reals}, language = {en} } @book{JongenMeerTriesch, author = {Jongen, Hubertus Theodor and Meer, Klaus and Triesch, Eberhard}, title = {Optimization Theory}, publisher = {Kluwer}, address = {Boston}, isbn = {978-1-402-08098-2}, pages = {XI, 443}, language = {en} } @inproceedings{ZhengRettingerGengler, author = {Zheng, Xizhong and Rettinger, Robert and Gengler, Romain}, title = {Ershov's hierarchy of real numbers}, series = {Mathematical foundations of computer science 2003, 28th international symposium MFCS, Bratislava, Slovakia, August 25 - 29, 2003}, booktitle = {Mathematical foundations of computer science 2003, 28th international symposium MFCS, Bratislava, Slovakia, August 25 - 29, 2003}, editor = {Rovan, Branislav}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-40671-9}, pages = {681 -- 690}, language = {en} } @inproceedings{Zheng, author = {Zheng, Xizhong}, title = {On the divergence bounded computable real numbers}, language = {en} } @inproceedings{ZhengBarmpalias, author = {Zheng, Xizhong and Barmpalias, George}, title = {On the monotonic computability of semi-computable real numbers}, language = {en} } @inproceedings{ZhengRettingerBraunmuehl, author = {Zheng, Xizhong and Rettinger, Robert and Braunm{\"u}hl, Burchard von}, title = {On the effective Jordan decomposability}, language = {en} } @inproceedings{Meer, author = {Meer, Klaus}, title = {On the complexity of some problems in interval arithmetic}, series = {Proceedings, 28th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 2003}, booktitle = {Proceedings, 28th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 2003}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-40671-9}, pages = {582 -- 591}, language = {en} } @incollection{JongenMeer, author = {Jongen, Hubertus Theodor and Meer, Klaus}, title = {Optimierung}, series = {Faszination Mathematik}, booktitle = {Faszination Mathematik}, editor = {Walz, Guido}, publisher = {Spektrum Akademischer Verlag}, address = {Heidelberg}, isbn = {3-8274-1419-9}, pages = {211 -- 216}, language = {de} } @misc{RettingerZheng, author = {Rettinger, Robert and Zheng, Xizhong}, title = {On the hierarchy and extension of monotonically computable real numbers}, series = {Journal of Complexity}, volume = {19}, journal = {Journal of Complexity}, number = {5}, issn = {0885-064X}, pages = {672 -- 691}, language = {en} } @misc{Zheng, author = {Zheng, Xizhong}, title = {On the Turing degrees of weakly computable real numbers}, series = {Journal of Logic and Computation}, volume = {13}, journal = {Journal of Logic and Computation}, number = {2}, issn = {0955-792X}, pages = {159 -- 172}, language = {en} } @article{Zheng, author = {Zheng, Xizhong}, title = {Recursive approximability of real numbers}, language = {de} } @misc{ZhengRettingerBraunmuehl, author = {Zheng, Xizhong and Rettinger, Robert and Braunm{\"u}hl, Burchard von}, title = {Effectively absolute continuity and effective Jordan decomposability}, series = {Electronic Notes in Theoretical Computer Science}, volume = {66}, journal = {Electronic Notes in Theoretical Computer Science}, number = {1}, issn = {1571-0661}, pages = {213 -- 224}, language = {en} }