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

Accepted Papers

The following papers have been accepted for presentation at CiE 2009. Some of these papers (indicated by LNCS logo) 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
LNCS logo 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
LNCS logo 89 Mathias Barra and Philipp Gerhardy Skolem + Tetration is well-ordered
  34 Hannah Bayer and Markus Nebel Evaluating algorithms according to their energy consumption
LNCS logo 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
LNCS logo 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
LNCS logo 74 Paul Brodhead and Bjørn Kjos-Hanssen The strength of the Grätzer-Schmidt theorem
LNCS logo 122 Paul Brodhead and Bjørn Kjos-Hanssen Numberings and randomness
LNCS logo 51 John Case and Samuel E. Moelius Program self-reference in constructive Scott subdomains
LNCS logo 91 Douglas Cenzer, Valentina Harizanov and Jeffrey Remmel Sigma-0-1 and Pi-0-1 equivalence structures
LNCS logo 60 Douglas Cenzer, Rebecca Weber and Guohua Wu Immunity for closed sets
LNCS logo 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
LNCS logo 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
LNCS logo 100 Ross Duncan and Simon Perdrix Graph states and the necessity of Euler decomposition
LNCS logo 13 Ömer Egecioglu and Oscar Ibarra On stateless multicounter machines
LNCS logo 38 Martín Escardó Computability of continuous solutions of higher-type equations
  61 Guido Fiorino Taming implications in Dummett logic
LNCS logo 54 Willem Fouché Fractals generated by algorithmically random Brownian motion
LNCS logo 102 Cameron Freer and Daniel Roy Computable exchangeable sequences have computable de Finetti measures
LNCS logo 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
LNCS logo 52 Mathieu Hoyrup and Cristóbal Rojas An application of Martin-Loef randomness to effective probability theory
LNCS logo 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
LNCS logo 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
LNCS logo 62 Gyesik Lee Relationship between Kanamori-McAloon principle and Paris-Harrington theorem
LNCS logo 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
LNCS logo 11 Klaus Meer On Ladner's result for a class of real machines with restricted use of constants
LNCS logo 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
LNCS logo 103 Jeff Paris and Alena Vencovská A general representation theorem for probability functions satisfying spectrum exchangeability
LNCS logo 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
LNCS logo 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
LNCS logo 106 Alla Sirokofskich Decidability of sub-theories of polynomials over a finite field
LNCS logo 123 Kohtaro Tadaki Chaitin \Omega numbers and halting problems
  95 Mohammad Torabi Dashti and Bahareh Badban Robust linear realizations of finite automata
LNCS logo 59 Trifon Trifonov Dialectica interpretation with fine computational control
LNCS logo 25 Andreas Weiermann A computation of the maximal order type of the term ordering on finite multisets
LNCS logo 87 Michael Weiss and Grégory Lafitte Constructing new aperiodic self-simulating tile sets
LNCS logo 63 Guohua Wu, Jiang Liu and Shengling Wang Infima of the d-r-e degrees
LNCS logo 20 Marius Zimand On generating independent random strings