Accepted Papers

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