TY - GEN ED - Brandstädt, Andreas ED - Köhler, Ekkehard ED - Meer, Klaus T1 - Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018 Y1 - 2018 SN - 978-3-030-00255-8 SN - 978-3-030-00256-5 PB - Springer International Publishing CY - Cham, Switzerland ER - TY - GEN A1 - Baartse, Martijn A1 - Meer, Klaus T1 - Interactive proofs and a Shamir-like result for real number computations T2 - Computational Complexity Y1 - 2018 U6 - https://doi.org/10.1007/s00037-018-0174-6 SN - 1016-3328 SN - 1420-8954 ER - TY - GEN A1 - Baartse, Martijn A1 - Meer, Klaus T1 - An algebraic proof of the real number PCP theorem T2 - Journal of Complexity N2 - 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. KW - Probabilistically checkable proofs KW - Real number model of computation KW - PCP theorem for NP over the reals KW - Testing trigonometric polynomials KW - Algebraic proofs Y1 - 2017 UR - http://www.sciencedirect.com/science/article/pii/S0885064X1630111X U6 - https://doi.org/10.1016/j.jco.2016.11.006 SN - 0885-064X VL - 40 SP - 34 EP - 77 ER - TY - JFULL ED - Meer, Klaus ED - Löwe, Benedikt ED - Macpherson, H. Dugald T1 - Mathematical Logic Quarterly Y1 - 2017 UR - http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1521-3870/issues SN - 1521-3870 VL - Vol. 63 IS - 1-2, 3-4, 5, 6 PB - Wiley-VCH CY - Berlin [u.a.] ER - TY - JFULL ED - Meer, Klaus ED - Novak, Erich ED - Dick, Josef ED - Hinrichs, Aicke ED - Ritter, Klaus ED - Sloan, Ian ED - Wasilkowski, Greg ED - Wozniakowski, Henryk T1 - Journal of Complexity Y1 - 2017 SN - 0885-064X VL - Vol. 38 - 43 PB - Elsevier CY - Amsterdam [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 - CHAP A1 - Baartse, Martijn A1 - Meer, Klaus ED - Faliszewski, Piotr ED - Muscholl, Anca ED - Niedermeier, Rolf T1 - Real Interactive Proofs for VPSPACE T2 - 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-64300 SN - 978-3-95977-016-3 SP - 14.1 EP - 14.13 PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH CY - Wadern ER - TY - JFULL ED - Meer, Klaus ED - Löwe, Benedikt ED - Macpherson, H. Dugald T1 - Mathematical Logic Quarterly Y1 - 2016 UR - http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1521-3870/issues SN - 1521-3870 VL - Vol. 62 IS - 1-2, 3, 4-5, 6 PB - Wiley-VCH CY - Berlin [u.a.] ER - TY - JFULL ED - Meer, Klaus ED - Novak, Erich ED - Dick, Josef ED - Hinrichs, Aicke ED - Ritter, Klaus ED - Sloan, Ian ED - Wasilkowski, Greg ED - Wozniakowski, Henryk T1 - Journal of Complexity Y1 - 2016 SN - 0885-064X VL - Vol. 32 - 37 PB - Elsevier CY - Amsterdam [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 -