Computability in Europe 2009 Mathematical Theory and Computational Practice Heidelberg, Germany, 19-24 July 2009 |

GeneralHome Programme Committee Organising Committee Sponsors Contact News Programme Committee |
ParticipationRegistration Venue Practical Information Accommodation Grants Photos Practical Information |
ProgrammeTime Table Tutorials and Plenary Talks Special Sessions Contributed Talks and Informal Presentations Workshop “Women in Computability” Contributed talks andInformal Presentations |
PublicationsPre- and Post-Conference Call for Papers Paper Submission Instructions for Authors Informal Presentations Pre- and Post-Conference |
CiEConference Description Association Conference Series Women in Computability Women in Computability |

The following papers have been accepted for presentation at CiE 2009. Some of these papers (indicated by ) have been accepted for publication in the pre-proceedings volume published in the Springer Lecture Notes in Computer Science series, the others will be published in our abstract booklet. All authors of papers presented at CiE 2009 may be invited to submit papers to one of the post-conference publications.

# | Author(s) | Title | |

109 | Kuanysh Abeshev and Serikzhan Badaev | Note on universal numberings | |

75 | Thomas Anberrée | First-order universality for real programs | |

108 | Ulavappa B. Angadi and M. Venkatesulu | Automatic classification of protein sequences into families using elongated K-mean spectral clustering | |

99 | Pablo Arrighi and Gilles Dowek | Intrinsic computability over algebraic structures | |

58 | Sergey Babenyshev, Vladimir Rybakov and Renate Schmidt | Temporal logic treating uncertainty and interacting agents with time indexes from Z | |

104 | Bahareh Badban | A Complete proof for ground term algebra with recognizers | |

92 | Mathias Barra | Relativised detour degrees | |

89 | Mathias Barra and Philipp Gerhardy | Skolem + Tetration is well-ordered | |

34 | Hannah Bayer and Markus Nebel | Evaluating algorithms according to their energy consumption | |

80 | David R. Bélanger | Structures of some strong reducibilities | |

49 | Josef Berger | A characterisation of BD-N | |

55 | Hendrik Blockeel and Robert Brijder | Learning non-confluent NLC graph grammar rules | |

67 | Manuel Bodirsky, Miki Hermann and Florian Richoux | Complexity of existential positive first-order logic | |

24 | Paul Brodhead and Douglas Cenzer | Effective capacity and randomness of closed sets | |

74 | Paul Brodhead and Bjørn Kjos-Hanssen | The strength of the Grätzer-Schmidt theorem | |

122 | Paul Brodhead and Bjørn Kjos-Hanssen | Numberings and randomness | |

51 | John Case and Samuel E. Moelius | Program self-reference in constructive Scott subdomains | |

91 | Douglas Cenzer, Valentina Harizanov and Jeffrey Remmel | Sigma-0-1 and Pi-0-1 equivalence structures | |

60 | Douglas Cenzer, Rebecca Weber and Guohua Wu | Immunity for closed sets | |

23 | Yijia Chen, Jörg Flum and Moritz Müller | Lower bounds for kernelizations and other preprocessing procedures | |

32 | Jingchao Chen | Iterative rounding for the closest string problem | |

70 | Pieter Collins | Computable types for dynamic systems | |

57 | Pieter Collins and Ivan Zapreev | Computable CTL for discrete-time and continuous-space dynamic systems | |

110 | Chris Conidis | The reverse mathematics of Artinian rings | |

69 | Stefan Dantchev and Barnaby Martin | Cutting planes and the parameter cutwidth | |

10 | Graçaliz Dimuro and Antonio Carlos Costa | Toward a semantical model of organization growth for multiagent systems | |

100 | Ross Duncan and Simon Perdrix | Graph states and the necessity of Euler decomposition | |

13 | Ömer Egecioglu and Oscar Ibarra | On stateless multicounter machines | |

38 | Martín Escardó | Computability of continuous solutions of higher-type equations | |

61 | Guido Fiorino | Taming implications in Dummett logic | |

54 | Willem Fouché | Fractals generated by algorithmically random Brownian motion | |

102 | Cameron Freer and Daniel Roy | Computable exchangeable sequences have computable de Finetti measures | |

98 | Tobias Gärtner and Günter Hotz | Computability of analytic functions with analytic machines | |

71 | Matthew Giorgi, Thomas Kent, Andrew Lewis and Andrea Sorbi | Empty intervals of enumeration degrees and strong minimal covers | |

93 | Nicolas Glade and Olivier Bastien | Robustness of single trail system-based wires for bio-processing architectures | |

30 | Binghui Guo, Wei Wei and Zhiming Zheng | Constraint message propagation dynamics of nonlinear Boolean equations | |

18 | Armin Hemmerling | Function operators spanning the arithmetical and the polynomial hierarchy - extended abstract | |

44 | Grzegorz Herman and Michael Soltys | Unambiguous functions in logarithmic space | |

53 | Thomas Hinze, Raffael Fassler, Gabi Escuela, Bashar Ibrahim and Stefan Schuster | Computation by synthetic cell signaling and oscillating processes modelled using mass-action kinetics | |

52 | Mathieu Hoyrup and Cristóbal Rojas | An application of Martin-Loef randomness to effective probability theory | |

8 | Sanjay Jain, Frank Stephan and Jason Teutsch | Index sets and universal numberings | |

29 | Xin Jiang, Shaoting Tang, Lili Ma, Zhanli Zhang and Zhiming Zheng | Random diffusion and congestion on weighted complex networks | |

27 | Norihiro Kamide | Strong normalization of program-indexed lambda calculus | |

17 | Takayuki Kihara and Kojiro Higuchi | Notions of reducibility for mass problems | |

79 | Jan Kluka and Paul J Voda | A simple and practical valuation tree calculus for first-order logic | |

37 | Nikolai Kosmatov | On computability and complexity of all-paths test generation: a practitioner’s point of view | |

21 | S. Krishna and Lakshmi Manasa | Determinization of a subclass of timed automata | |

7 | Oleg V. Kudinov and Victor L. Selivanov | A Gandy theorem for abstract structures and applications to first-order definability | |

6 | Oleg V. Kudinov, Victor L. Selivanov and Anton Zhukov | Definability of closure operations in the $h$-Quasiorder of labeled forests | |

72 | James Lambert | The relationship between measurability and computability | |

62 | Gyesik Lee | Relationship between Kanamori-McAloon principle and Paris-Harrington theorem | |

85 | Andrew Lewis, André Nies and Andrea Sorbi | The first order theories of the Medvedev and the Muchnik lattice | |

50 | Chung-Chih Li | Union theorems in type-2 computation | |

65 | Remco Loos, Florin Manea and Victor Mitrana | Small universal accepting networks of evolutionary processors | |

19 | Yanfang Ma and Yixiang Chen | Two-thirds bisimulation indexes | |

88 | J. Raymundo Marcial-Romero, Claudia Zepeda, J. A. Hernández, Héctor A. Montes and David Linares | An implementation of exact real number computation based on LRT | |

11 | Klaus Meer | On Ladner's result for a class of real machines with restricted use of constants | |

46 | Alexander Melnikov | Relatively categorical completely decomposable torsion-free Abelian groups | |

82 | Vincent C. Müller | Mechanical computation vs computation | |

73 | Benedek Nagy | On a hierarchy of $5' \to 3'$ sensing WK finite automata languages | |

45 | Juan Ospina | Generalized Temperley-Lieb algebras and quantum computation | |

103 | Jeff Paris and Alena Vencovská | A general representation theorem for probability functions satisfying spectrum exchangeability | |

101 | Soumya Paul, R. Ramanujam and Sunil Easaw Simon | Stability under strategy switching | |

90 | Florian Pelupessy and Andreas Weiermann | Ackermannian lower bounds for lengths of bad sequences of monomial ideals over polynomial rings in two variables | |

81 | Mikhail Peretyatkin | Effective pseudo-indecomposability of Tarski-Lindenbaum algebras of predicate calculi over finitary similarity relation of theories | |

76 | G. Michele Pinna | Petri nets unfoldings and the individual/collective token philosophy | |

77 | Ian Pratt-Hartmann and Ivo Duentsch | Functions definable by arithmetic circuits | |

86 | Vadim Puzarenko | One classical semilattice in admissible sets | |

33 | Eleonora Riva Sanseverino, Roberto Candela, Giuseppe Fileccia Scimemi and Giulio Cottone | Lévy flights for ant colony optimization in continuous domains | |

28 | Pavel Semukhin | Prime Models of finite computable dimension | |

106 | Alla Sirokofskich | Decidability of sub-theories of polynomials over a finite field | |

123 | Kohtaro Tadaki | Chaitin \Omega numbers and halting problems | |

95 | Mohammad Torabi Dashti and Bahareh Badban | Robust linear realizations of finite automata | |

59 | Trifon Trifonov | Dialectica interpretation with fine computational control | |

25 | Andreas Weiermann | A computation of the maximal order type of the term ordering on finite multisets | |

87 | Michael Weiss and Grégory Lafitte | Constructing new aperiodic self-simulating tile sets | |

63 | Guohua Wu, Jiang Liu and Shengling Wang | Infima of the d-r-e degrees | |

20 | Marius Zimand | On generating independent random strings |