zbMATH — the first resource for mathematics

Logical approaches to computational barriers. Second conference on computability in Europe, CiE 2006, Swansea, UK, June 30–July 5, 2006. Proceedings. (English) Zbl 1102.68002
Lecture Notes in Computer Science 3988. Berlin: Springer (ISBN 3-540-35466-2/pbk). xv, 608 p. (2006).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding conference has been reviewed (see Zbl 1078.68002).
Indexed articles:
Ábrahám, Erika; Grüner, Andreas; Steffen, Martin, Heap-abstraction for an object-oriented calculus with thread classes, 1-10 [Zbl 1145.68380]
Avron, Arnon, From constructibility and absoluteness to computability and domain independence, 11-20 [Zbl 1145.03328]
Backhouse, Roland, Datatype-generic reasoning, 21-34 [Zbl 1145.68381]
Berger, Josef, The logical strength of the uniform continuity theorem, 35-39 [Zbl 1145.03339]
Bergstra, J. A., Elementary algebraic specifications of the rational function field, 40-54 [Zbl 1145.68465]
Brodhead, Paul; Cenzer, Douglas; Dashti, Seyyed, Random closed sets, 55-64 [Zbl 1145.68437]
Brünnler, Kai, Deep inference and its normal form of derivations, 65-74 [Zbl 1145.03333]
Cenzer, Douglas; Uddin, Zia, Logspace complexity of functions and structures, 75-84 [Zbl 1145.03314]
Chernov, Alexey; Schmidhuber, Jürgen, Prefix-like complexities and computability in the limit, 85-93 [Zbl 1145.68412]
Dahlgren, Fredrik, Partial continuous functions and admissible domain representations, 94-104 [Zbl 1145.03329]
Dal Lago, Ugo; Martini, Simone, An invariant cost model for the lambda calculus, 105-114 [Zbl 1145.68375]
Dantchev, Stefan, On the complexity of the Sperner lemma, 115-124 [Zbl 1145.03334]
Davis, Martin, The Church-Turing thesis: Consensus and opposition, 125-132 [Zbl 1145.03300]
Dawson, John W. jun., Gödel and the origins of computer science, 133-136 [Zbl 1145.03301]
de Miguel Casado, Gregorio; García Chamizo, Juan Manuel, The role of algebraic models and type-2 theory of effectivity in special purpose processor design, 137-146 [Zbl 1145.68315]
Delvenne, Jean-Charles, Turing universality in dynamical systems, 147-152 [Zbl 1145.03318]
Doty, David, Every sequence is decompressible from a random one, 153-162 [Zbl 1145.03325]
Durand-Lose, Jérôme, Reversible conservative rational abstract geometrical computation is Turing-universal, 163-172 [Zbl 1117.03044]
Dyckhoff, Roy; Lengrand, Stéphane, LJQ: a strongly focused calculus for intuitionistic logic, 173-185 [Zbl 1133.03029]
Ehrhard, Thomas; Regnier, Laurent, Böhm trees, Krivine’s machine and the Taylor expansion of lambda-terms, 186-197 [Zbl 1130.68054]
Franzén, Torkel, What does the incompleteness theorem add to the unsolvability of the halting problem?, 198 [Zbl 1145.03319]
Gherardi, Guido, An analysis of the lemmas of Urysohn and Urysohn-Tietze according to effective Borel measurability, 199-208 [Zbl 1145.03340]
Harris, Charles M., Enumeration reducibility with polynomial time bounds, 209-220 [Zbl 1145.03326]
Hou, Tie, Coinductive proofs for basic real computation, 221-230 [Zbl 1145.68413]
Jacobé de Naurois, Paulin, A measure of space for computing over the reals, 231-240 [Zbl 1145.68424]
Köbler, Johannes, On graph isomorphism for restricted graph classes, 241-256 [Zbl 1145.68435]
Koepke, Peter, Infinite time register machines, 257-266 [Zbl 1143.03357]
Korovina, Margarita; Vorobjov, Nicolai, Upper and lower bounds on sizes of finite bisimulations of Pfaffian hybrid systems, 267-276 [Zbl 1145.68469]
Krajíček, Jan, Forcing with random variables and proof complexity, 277-278 [Zbl 1145.03335]
Kristiansen, Lars, Complexity-theoretic hierarchies, 279-288 [Zbl 1145.03320]
Kudinov, Oleg V.; Selivanov, Victor L., Undecidability in the homomorphic quasiorder of finite labeled forests, 289-296 [Zbl 1145.03307]
Laplante, Sophie, Lower bounds using Kolmogorov complexity, 297-306 [Zbl 1145.68429]
Lewis, Andrew E. M., The jump classes of minimal covers, 307-318 [Zbl 1145.03323]
Löwe, Benedikt, Space bounds for infinitary computation, 319-329 [Zbl 1145.68415]
Makowsky, J. A., From a zoo to a zoology: Descriptive complexity for graph polynomials, 330-341 [Zbl 1145.68432]
Martin, Barnaby; Madelaine, Florent, Towards a trichotomy for quantified \(H\)-coloring, 342-352 [Zbl 1145.68436]
Mayordomo, Elvira, Two open problems on effective dimension, 353-359 [Zbl 1145.68425]
Meer, Klaus, Optimization and approximation problems related to polynomial system solving, 360-367 [Zbl 1145.68416]
Meer, Klaus; Ziegler, Martin, Uncomputability below the real halting problem, 368-377 [Zbl 1145.68417]
Michaelson, Greg; Cockshott, Paul, Constraints on hypercomputation, 378-387 [Zbl 1145.68418]
Moser, Philippe, Martingale families and dimension in P, 388-397 [Zbl 1144.68319]
Németi, István; Andréka, Hajnal, Can general relativistic computers break the Turing barrier?, 398-412 [Zbl 1145.68419]
Ng, Keng Meng; Stephan, Frank; Wu, Guohua, Degrees of weakly computable reals, 413-422 [Zbl 1145.68420]
Oliva, Paulo, Understanding and using Spector’s bar recursive interpretation of classical analysis, 423-434 [Zbl 1145.68421]
Peshev, Peter; Skordev, Dimiter, A subrecursive refinement of the fundamental theorem of algebra, 435-444 [Zbl 1145.03321]
Ponse, Alban; van der Zwaag, Mark B., An introduction to program and thread algebra, 445-458 [Zbl 1131.68411]
Prunescu, Mihai, Fast quantifier elimination means P = NP, 459-470 [Zbl 1145.03312]
Schröder, Matthias, Admissible representations in computable analysis, 471-480 [Zbl 1145.03330]
Schuster, Peter; Zappe, Júlia, Do Noetherian modules have Noetherian basis functions?, 481-489 [Zbl 1145.03342]
Schwichtenberg, Helmut, Inverting monotone continuous functions in constructive analysis, 490-504 [Zbl 1137.03326]
Setzer, Anton, Partial recursive functions in Martin-Löf type theory, 505-515 [Zbl 1145.03322]
Sevenster, Merlijn; Tulenheimo, Tero, Partially ordered connectives and \(\Sigma^{1}_{1}\) on finite models, 516-525 [Zbl 1145.03313]
Krishna, Shankara Narayanan, Upper and lower bounds for the computational power of P systems with mobile membranes, 526-535 [Zbl 1145.68414]
Sieg, Wilfried, Gödel’s conflicting approaches to effective calculability, 536-537 [Zbl 1145.03302]
Solon, Boris, Co-total enumeration degrees, 538-545 [Zbl 1145.03327]
Soskova, Alexandra A., Relativized degree spectra, 546-555 [Zbl 1142.03353]
Weiermann, Andreas, Phase transition thresholds for some natural subclasses of the computable functions, 556-570 [Zbl 1110.03052]
Welch, P. D., Non-deterministic halting times for Hamkins-Kidder Turing machines, 571-574 [Zbl 1136.03322]
Zach, Richard, Kurt Gödel and computability theory, 575-583 [Zbl 1145.03303]
Zheng, Xizhong, A computability theory of real numbers, 584-594 [Zbl 1145.03341]
Zucker, J. I., Primitive recursive selection functions over abstract algebras, 595-606 [Zbl 1145.03331]

68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
00B25 Proceedings of conferences of miscellaneous specific interest
Full Text: DOI