Computing and Complexity

Tobias Gärtner. Representation Theorems for Analytic Machines |

Mihai Prunescu. Triangular perplexity and a stairway to heaven |

Tomer Kotek and Johann Makowsky. Definability of Combinatorial Functions and Their Linear Recurrence Relations |

Saugata Basu and Thierry Zell. Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem |

Oleg Kudinov, Victor Selivanov and Anton Zhukov. Undecidability in Weihrauch Degrees |

Eryk Kopczynski. Complexity of Problems of Commutative Grammars |

Pawel Parys. Some results on complexity of mu-calculus evaluation in the black-box model |

Saeed Salehi. Herbrand Consistency of ${\rm I\Delta_0}$ and ${\rm I\Delta_0}+\Omega_1$ |

Markus Lohrey, Dietrich Kuske and Jiamou Liu. The Isomorphism Problem On Classes of Automatic Structures |

Victor Selivanov. Fine Hierarchies via Priestley Duality |

Olaf Beyersdorff, Arne Meier, Sebastian Mueller, Michael Thomas and Heribert Vollmer. Proof Complexity of Propositional Default Logic |

André Souto, Luis Antunes and Andreia Teixeira. A characterization of one-way functions based on time-bounded Komogorov complexity |

Wesley Calvert and Russell Miller. Noncomputable Functions in the Blum-Shub-Smale Model |

Satoru Kuroda. Complete Problems and Bounded Arithmetic for LOGCFL |

Yijia Chen, Joerg Flum and Moritz Mueller. On Optimal Algorithms for SAT |

Bruno COURCELLE and Irène DURAND. Tractable constructions of finite automata from monadic second-order formulas |

Arno Pauly. Nash Equilibria and Fixed Points in the BSS-Model |

Mathieu Hoyrup. Randomness and the ergodic decomposition |

Barnaby Dawson. How definitions, equivalent for Turing machines, cease to be equivalent, when generalized to Ordinal Time Turing Machines |

Tim Fischbach and Peter Koepke. An Analogue of the Church-Turing Thesis for Computable Ordinal Functions |

Ilia Averbouch, Johann Makowsky and Peter Tittmann. A Case Study in Graph Polynomials: The Subgraph Component Polynomial |

Sam Sanders and Andreas Weiermann. UNBOUNDED ARITHMETIC |

Cameron Donnay Hill. Efficiently inverting the $L^2$-invariant through stability theory |

Peter Koepke and Gregor Weckbecker. Ordinal Register Machines and Combinatorial Principles in the Constructible Universe |

Katrin Tent and Martin Ziegler. Computable functions on the reals |

Jan Johannsen. Lower bounds for width-restricted clause learning |

Peter Koepke and Benjamin Seyfferth. A Characterization of Delta^1_2 Pointclasses Via Ordinal Machines |

Artur Wdowiarski. On Trasitive Closure Operators in Finite Order Logic |

Marcin Mostowski. Classification of the classes of finite models in Tarski' style |

Margarita Korovina. Computability over Positive Predicate Structures |

Anuj Dawar and Bjarki Holm. Pebble Games for Rank Logics |

Peter Scheiblechner. Comparison of Complexity over the Real vs. Complex Numbers |

Zofia Adamowicz and Konrad Zdanowski. Lower bounds for the provability of Herbrand consistency in weak arithmetics |

Oleg Kudinov and Victor Selivanov. A Logic to capture P-time computability on Cantor space |

websites: Arnold Beckmann | 2010-01-06 |