Logical Approaches to Barriers in
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