TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn ED - Beckmann, Arnold ED - Mitrana, Victor ED - Soskova, Mariya T1 - Some results on interactive proofs for real computations T2 - Evolving Computability 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015, Proceedings Y1 - 2015 UR - http://www.springer.com/in/book/9783319200279 SN - 978-3-319-20027-9 U6 - https://doi.org/10.1007/978-3-319-20028-6 SP - 107 EP - 116 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Naif, Ameen ED - Gopal, T. V. ED - Agrawal, Manindra ED - Li, Angsheng ED - Cooper, Stuart Barry T1 - Generalized Finite Automata over Real and Complex Numbers T2 - Theory and Applications of Models of Computation 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014, Proceedings Y1 - 2014 UR - http://www.springer.com/us/book/9783319060880 SN - 978-3-319-06088-0 U6 - https://doi.org/10.1007/978-3-319-06089-7 SP - 168 EP - 187 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Baartse, Martijn ED - Hirsch, Edward ED - Kuznetsov, Sergei O. ED - Pin, Jean-Éric ED - Vereshchagin, Nikolay T1 - Testing Low Degree Trigonometric Polynomials T2 - Computer Science - Theory and Applications 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014, Proceedings Y1 - 2014 UR - http://www.springer.com/de/book/9783319066851 SN - 978-3-319-06685-1 U6 - https://doi.org/10.1007/978-3-319-06686-8 SP - 77 EP - 96 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus A1 - Naif, Ameen ED - Dediu, Adrian-Horia ED - Janoušek, Jan ED - Martín-Vide, Carlos ED - Truthe, Bianca T1 - Periodic Generalized Automata over the Reals T2 - Language and Automata Theory and Applications 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings Y1 - 2016 UR - http://www.springer.com/de/book/9783319299990 SN - 978-3-319-29999-0 U6 - https://doi.org/10.1007/978-3-319-30000-9 SP - 168 EP - 180 PB - Springer International Publishing CY - Berlin [u.a.] ER - TY - GEN A1 - Meer, Klaus A1 - Lickteig, Thomas T1 - Semi-algebraic complexity - Additive complexity of matrix computational tasks T2 - Journal of Complexity N2 - This paper is devoted to the study of lower bounds on the inherent number of additions and subtractions necessary to solve some natural matrix computational tasks such as computing the nullspace, some band transformation, and some triangulation of a givenm×mmatrix. The additive complexities of such tasks are shown to grow asymptotically like that of them×mmatrix multiplication. The paper is a continuation of an earlier paper by the authors, and also of 4where multiplicative complexity has been considered. We also propose a formalization of semialgebraic computational tasks. Y1 - 1997 UR - http://www.sciencedirect.com/science/article/pii/S0885064X97904301 U6 - https://doi.org/10.1006/jcom.1997.0430 SN - 0885-064X VL - 13 IS - 1 SP - 83 EP - 107 ER - TY - GEN A1 - Meer, Klaus A1 - Malajovich, Gregorio T1 - On the structure of NP_C T2 - SIAM Journal on Computing KW - complexity KW - NP-completeness KW - BSS machines over C KW - Hilbert Nullstellensatz Y1 - 1999 UR - http://epubs.siam.org/action/showAbstract?page=27&volume=28&issue=1&journalCode=smjcat& U6 - https://doi.org/10.1137/S0097539795294980 SN - 1095-7111 VL - 28 IS - 1 SP - 27 EP - 35 ER - TY - CHAP A1 - Meer, Klaus ED - Prívara, Igor ED - Ružička, Peter T1 - Counting problems over the reals T2 - Mathematical foundations of computer science 1997, 22nd international symposium, proceedings, MFCS '97, Bratislava, Slovakia, August 25 - 29, 1997 N2 - In this paper we introduce a complexity theoretic notion of counting problems over the real numbers. We follow the approaches of Blum, Shub, and Smale. Y1 - 1997 UR - http://www.springer.com/us/book/9783540634379?wt_mc=ThirdParty.SpringerLink.3.EPR653.About_eBook SN - 978-3-540-63437-9 U6 - https://doi.org/10.1007/BFb0029983 SP - 398 EP - 407 PB - Springer CY - Berlin [u.a.] ER - TY - CHAP A1 - Meer, Klaus ED - Kutylowski, Miroslaw ED - Leszek, Pacholski ED - Wierzbicki, Tomasz T1 - Query languages for real number databases based on descriptive complexity over R T2 - Mathematical foundations of computer science 1999, 24th international symposium, MFCS '99, Szklarska Pore̜ba, Poland, September 6 - 10, 1999, proceedings N2 - We propose the study of query languages for databases involving real numbers as data (called real number databases in the sequel). As main new aspect our approach is based on real number complexity theory as introduced in [8] and descriptive complexity for the latter developed in [17]. Using this formal framework a uniform treatment of query languages for such databases is obtained. Precise results about both the data- and the expression-complexity of several such query languages are proved. More explicitly, relying on descriptive complexity theory over ℝ gives the possibility to derive a hierarchy of complete languages for most of the important real number complexity classes. A clear correspondence between different logics and such complexity classes is established. In particular, it is possible to formalize queries involving in a uniform manner real spaces of different dimensions. This can be done in such a way that the logical description exactly reflects the computational complexity of a query. The latter might circumvent a problem appearing in some of the former approaches dealing with semi-algebraic databases (see [20] , [18]), where the use of first-order logic over real-closed fields can imply inefficiency as soon as the dimension of the underlying real space is not fixed - no matter whether the query under consideration is easy to compute or not. Y1 - 1999 UR - http://link.springer.com/chapter/10.1007%2F3-540-48340-3_2 SN - 978-3-540-66408-6 U6 - https://doi.org/10.1007/3-540-48340-3_2 SP - 12 EP - 22 PB - Springer CY - Berlin [u.a.] ER - TY - GEN A1 - Meer, Klaus T1 - Computations over Z and R : a comparison T2 - Journal of Complexity N2 - Regarding real number models of computation may be a helpful way to get deeper insight into the classical theory over Z. Therefore it seems useful to study the complexity of classical problems in the real model. In this connection, the problem of deciding the existence of a nonnegative zero for certain polynomials plays an important part because a lot of NP-problems over Z can be polynomial reduced to it. Y1 - 1990 UR - http://www.sciencedirect.com/science/article/pii/0885064X90900226 U6 - https://doi.org/10.1016/0885-064X(90)90022-6 SN - 0885-064X VL - 6 IS - 3 SP - 256 EP - 263 ER - TY - GEN A1 - Meer, Klaus T1 - A note on a $ P \neq NP-$ result in a restricted class of real machines T2 - Journal of Complexity N2 - For a class of real machines using only linear functionals as computations and equality-tests, we show that the classes P and NP differ. Y1 - 1992 UR - http://www.sciencedirect.com/science/article/pii/0885064X9290007X U6 - https://doi.org/10.1016/0885-064X(92)90007-X SN - 0885-064X VL - 8 IS - 4 SP - 451 EP - 453 ER -