CiE 2012 - Home page

Schedule of Contributed Talks

		Session 1 (BLT) Chair: Cholak	Session 2 (CLT) Chair: Jonoska	Session 3 (ASA) Chair: Cooper	Session 4 (ASB) Chair: Perdrix	Session 5 (ASC) Chair: Knight	Session 6 (LEH) Chair: Wu	Session 7 (SS1) Chair: Beckmann

Tue June 19 morning	11:00:00	Vladimir Podolskii Lower Bound on Weights of Large Degree Threshold Functions	Darya Verveyko and Andrey Verisokin Computer Simulation of Three-Dimensional Reaction-Diffusion Models. Case Study: Glycolytic Reaction in Open Spatial Reactor	Laurentiu Leustean and Ulrich Kohlenbach Applications of proof mining in nonlinear ergodic theory	Anahit Chubaryan and Armine Chubaryan Resolution Systems with Substitution Rules	Douglas Bridges and Robin Havea Square roots and powers in constructive Banach algebra theory	Ningning Peng and Kojiro Higuchi and Takeshi Yamazaki and Kazuyuki Tanaka Relative Randomness for Martin-Löf random Sets	Yoshii Keisuke and Kazuyuki Tanaka Infinite Games and Transfinite Recursion of Multiple Inductive Definitions
	11:15:00	Stefano Mazzanti Bases for AC0 and other Complexity Classes	Thomas Woolley and Ruth Baker and Eamonn Gaffney and Philip Maini Stochastic reaction and diffusion on growing domains: understanding the breakdown of robust pattern formation	Pierre Guillon and Charalampos Zinoviadis Densities and entropies in cellular automata	George Metcalfe and Christoph Röthlisberger Unifiability and Admissibility in Finite Algebras	Mikhail Peretyatkin On the Tarski-Lindenbaum algebra of the class of all strongly constructivizable prime models	Kenshi Miyabe An integral test for Schnorr randomness and its applications	Peter Schuster and Matthew Hendtlass A direct proof of Wiener's theorem
	11:30:00	Sebastian Eberhard Applicative theories for logarithmic complexity classes	Andrey Verisokin and Darya Verveyko and Eugene Postnikov Mathematical Model of Chaotic Oscillations and Oscillatory Entrainment in Glycolysis Originated from Periodic Substrate Supply	Les Hatton Equilibriation of information in software systems	Michael Beeson Logic of ruler and compass constructions	Nurlan Kogabaev On Uniform Computability in Familiar Classes of Projective Planes	Tommaso Flaminio and Hykel Hosni De Finetti's bets on partially evaluated Kripke frames	Joerg Zimmermann and Armin Cremers Making Solomonoff Induction Effective or You Can Learn What You Can Bound
	11:45:00	Russell Miller and Keng Meng Ng Finitary reducibility on equivalence relations	Ranjit Kumar Upadhyay and Sharada Nandan Raw Emergence of Spatial Patterns in a Model of Wetland Ecosystem: Application to Keoladeo National Park (KNP) and India	Joost Joosten Turing Machines and revisited	Grant Passmore and Paul Jackson Abstract Partial Cylindrical Algebraic Decomposition I: The Lifting Phase	Margarita Leontyeva On Existence of Strongly Computable Copies in Class of Boolean Algebras	Douglas Cenzer Bounded Primitive Recursive Randomness	Makoto Fujiwara and Kojiro Higuchi and Takayuki Kihara Recursive marriage theorems and reverse mathematics
	12:00:00	Magnus Gausdal Find and Joan Boyar Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators	Eugene Postnikov Computational model based on meteorological data for forecast of influenza-like activity	Duilio D'Alfonso Algorithmic complexity and entropy and the discovery of causal correlations	Ugo Dal Lago and Tobias Heindel and Damiano Mazza and Daniele Varacca Computational Complexity of Interactive Behaviors	Asylkhan Khisamiev $\Sigma$-complete structures and universal functions	Benoît Monin Von Neumann's Biased Coin Revisited	Josef Berger When is the denial inequality an apartness relation?
	12:15:00	Marcin J. Schroeder Structural versus Quantitative Characteristics of Information in Information Processing: Information Integration	Loizos Michael Ant Collectives as Computers	Hristo Ganchev The enumeration degrees of semi-recursive sets	Karel Chvalovský Linearization of Proofs in Propositional Hilbert Systems	Andrey Sariev The Omega-Turing degrees	Bruno Bauwens A simple proof that complexity of complexity can be large and and that some strings have maximal plain Kolmogorov complexity and non-maximal prefix-free complexity.	Maarten Mckubre-Jordens and Douglas Bridges Solving the Dirichlet Problem Constructively

		Session 1 (BLT) Chair: Bishop	Session 2 (CLT) Chair: Stanett	Session 3 (ASA) Chair: Cenzer	Session 4 (ASB) Chair: Case	Session 5 (ASC) Chair: Zenil	Session 6 (LEH) Chair: Joosten	Session 7 (SS1) Chair: Loewe
Tue June 19 afternoon	17:30:00	Anargyros Sarafopoulos Shape a Language for IFS	Hideki Tsuiki Multi-Head Extension of the Turing Machine for Computation over Continuous Spaces	Kerstin Andersson Numerical evaluation of the average number of successive guesses	Jose Espirito Santo Intuitionistic asymmetry: how the CBN/CBV duality breaks	Catherine Stinson Computational Models as Mechanistic Explanations	Yasushi Okuno and Shinnosuke Seki On the behavior of tile assembly system at high temperatures	Roussanka Loukanova Computational Syntax-Semantics Interface of Passive Forms with The Language of Acyclic Recursion
	17:45:00	Alison Pease and Simon Colton and John Charnley The Turing Test and Computational Creativity	Takayuki Kihara A hierarchy of immunity and density for sets of reals	Antoine Taveneaux and Bjørn Kjos-Hanssen and Neil Thapen How much randomness is needed for statistics?	Michael Gabbay A simple and complete model theory for intensional and extensional untyped lambda-equality	Ranjit Nair Computablity and physics and logic	Oznur Yasar Diner and Dariusz Dereniowski and Danny Dyer Complexity of Fast Searching	Loizos Michael Computability of Narrative
	18:00:00	Ashish Umre and Ian Wakeman Dynamics of Agent Interaction: In search of strategies for optimal information sharing	Arno Pauly Multi-valued functions in Computability Theory	Kenneth Johnson and John V. Tucker A Model of Computing as a Service for Cost Analysis	Assel Altayeva and Iman Poernomo Towards a Type Theory of Predictable Assembly	Christopher Porter On Analogues of the Church-Turing Thesis in Algorithmic Randomness	Alexander Golovnev Approximating Asymmetric Metric TSP in Exponential Time	Jeffrey Watumull The Linguistic Turing Machine
	18:15:00	Sabine Broda and António Machiavelo and Nelma Moreira and Rogério Reis Average Case Complexity of epsilon-NFA's	Hajnal Andréka and István Németi Turing-degree of first-order logic FOL and reducing FOL to a propositional logic				Simon Perdrix A Lower Bound on the Minimal Resources for Measurement-based Quantum Computation

		Session 1 (BLT) Chair: Panangaden	Session 2 (CLT) Chair: Longo	Session 3 (ASA) Chair: Hutter	Session 4 (ASB) Chair: Welch	Session 5 (ASC) Chair: Verbrugge	Session 6 (LEH) Chair: Brattka	Session 7 (SS1) Chair: Sieg

Wed June 20 morning	10:30:00	David Edward Bruschi and Ivette Fuentes and Jorma Louko and Antony Lee and Andrzej Dragan and Nicolai Friis Cavity motion affects entanglement	Samuel Moelius Characteristics of Minimal Effective Programming Systems	Richard Booth On Turing Scores	Julian-Steffen Müller Complexity of Model Checking in Modal Team Logic	Isabel Cafezeiro and Ivan Da Costa Marques Interweavings of Alan Turing's Mathematics and Sociology of Knowledge	Ken-Ichi Hiraga and Kota Ikeda and Takashi Miura Slow and steady wins the race: relationship between accuracy and speed of Turing pattern formation	Fred Gruau Self Developing Network
	10:45:00	Yun Shang and Xian Lu and Ruqian Lu Closure Properties of Quantum Turing Languages	Marcel Celaya and Frank Ruskey An Undecidable Nested Recurrence Relation	Sorin Istrail and Solomon Marcus Turing and von Neumann's Brains and their Computers	Petar Iliev and Wiebe Van Der Hoek and Barteld Kooi On the Relative Succinctness of Two Extensions by Definitions of Multimodal Logic	Cameron Buckner Heuristics and Intelligence: Realizing Turing's Vision	Dirk Sudholt The Analysis of Evolutionary Algorithms: Why Evolution is Faster With Crossover	Henson Graves Structure Diagrams in Type Theory
	11:00:00	Luís Tarrataca and Andreas Wichert Iterative Quantum Tree Search	Emmanuel Jeandel On Immortal Configurations in Turing Machines	Paul Cockshott and Greg Michaelson Infinity and Interaction and Turing Machines	Ilayda Ates and Çigdem Gencer On Models of the Modal Logic GL	Alison Pease and Ursula Martin Summary of an ethnographic study of the third Mini-Polymath project	Joseph Shipman and John H. Conway Geometric Models of Computation	Arturo Carsetti Eigenforms and natural computing and morphogenesis
	11:15:00	Sylvain Gravier and Jérôme Javelle and Mehdi Mhalla and Simon Perdrix Quantum Secret Sharing with Graph States	Victor Ocasio Turing Computable Embeddings and Coding Families of Sets	Peter Wegner Alan Turing and Maurice Wilkes	Edgar Daylight Book Presentation: `The Dawn of Software Engineering: from Turing to Dijkstra'	Manuel Mazzara and Antonio Marraffa and Luca Biselli and Simona De Nicola and Luca Chiarabini and Georgios Papageorgiou Social Networks and Collective Intelligence	Francisco Hernández-Quiroz and Pablo Padilla-Longoria Some constraints on the physical realizability of a mathematical construction	Masaharu Mizumoto How to Accept Turing's Thesis without Proof or Conceptual Analysis and without also Feeling Qualms

		Session 1 (BLT) Chair: Beckmann	Session 2 (CLT) Chair: Lubarsky	Session 3 (ASA) Chair: Downey	Session 4 (ASB) Chair: Michaelson	Session 5 (ASC) Chair: Carsetti	Session 6 (LEH) Chair: Stanett	Session 7 (SS1) Chair: Daylight

Thu June 21 morning	10:30:00	Yijia Chen and Jörg Flum and Moritz Mueller Hard Instances of Algorithms and Proof Systems	Fernando Ferreira A short note on Spector's consistency proof of analysis	Alexander Kartzow and Jiamou Liu and Markus Lohrey Tree-Automatic Well-Founded Trees	Ludwig Staiger A Correspondence Priciple for Exact Constructive Dimension	Oron Shagrir Who is the human computer?	Péter Németi and Gergely Székely Existence of Faster Than Light Signals Implies Hypercomputation Already in Special Relativity	Michael Fiske Turing Incomputable Computation
	10:45:00	F. Félix Lara-Martín and Andrés Cordón-Franco Local Induction and Provably Total Computable Functions: a Case Study	Akitoshi Kawamura and Norbert Müller and Carsten Rösnick and Martin Ziegler Uniformly Polynomial-time Computable Operators on Analytic Functions	John Case and Sanjay Jain and Samuel Seah and Frank Stephan Automatic functions and linear time and learning	Vladimir Kanovei On effective sigma-boundedness and sigma-compactness	Gordana Dodig Crnkovic Alan Turing's Legacy: Info-Computational Philosophy of Nature	Merlin Carl The distribution of the ITRM-recognizable reals	Marc Groz Systems and Methods for Data and Algorithm Protection
	11:00:00	Alexander Kulikov and Olga Melanich and Ivan Mihajlin A $5n-o(n)$ Lower Bound on the Circuit Size over $U_2$ of a Linear Boolean Function	Sam Sanders Nonstandard Analysis: A New Way to Compute	Martin Huschenbett Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable	Armando Matos and Andreia Teixeira Lossless compressors: Degree of compression and optimality	Carolina Blasio and João Marcos Logical Agency: consulting instead of collecting	Benjamin Rin The computational strengths of alpha-length infinite time Turing machines	Leon N Cooper and Sorin Istrail Mental Experience and The Turing Test: This Double Face is the Face of Mathematics
	11:15:00	A.C. Cem Say and Abuzer Yakaryilmaz Finite state verifiers with constant randomness	Andreas Weiermann and Alan Woods Some natural zero one laws for ordinals below $\varepsilon_0$	Ekaterina Fokina and Pavel Semukhin Structures presentable by various types of automata	Peter Cholak and Damir Dzhafarov and Jeffry Hirst Computable Mathias genericity	Nir Fresco Digital Computation as Instructional Information Processing	Fotini Markopoulou The Computing Spacetime	Rema Padman and Daniel Neill and Chris Harle Information Visualization for Cognitively Guided Health Risk Assessment

		Session 1 (BLT) Chair: Andreka	Session 2 (CLT) Chair: Bournez	Session 3 (ASA) Chair: Freer	Session 4 (ASB) Chair: Ditchev	Session 5 (ASC) Chair: Boas	Session 6 (LEH) Chair: Normann	Session 7 (SS1) Chair: Bonnizoni

Fri June 22 morning	10:30:00	Hartmut Ehrig and Claudia Ermel and Falk Hüffner and Rolf Niedermeier and Olga Runge Confluence in Data Reduction: Bridging Graph Transformation and Kernelization	Peter Koepke and Benjamin Seyfferth Towards a theory of infinite time Blum-Shub-Smale machines	Sori Lee Trees for Subtoposes of the Effective Topos	Paola Zizzi The modality 'Future' for Probably true propositions	Pieter Adriaans Facticity as the amount of self-descriptive information in a data set	Lars Kristiansen Degrees of Total Algorithms versus Degrees of Honest Functions	Nikolay Kosovskiy Polynomial-Time Modifications of Church-Turing Thesis for Three Programming Languages
	10:45:00	Sepp Hartung and André Nichterlein NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs	Peter Koepke and Andrey Morozov On the Computational Strength of Infinite Time Blum Shub Smale Machines	Amin Farjudian A Semantic Framework for Real Computation with Polynomial Enclosures	Mitko Yanchev Part restrictions: adding new expressiveness in Description Logics	Loizos Michael WebSense: Making Sense of the Web	Kojiro Higuchi and Takayuki Kihara Effective strong nullness and effectively closed sets	Gregorio de Miguel Casado and Manuel González Bedia Revamping the Turing Test by Computing Interaction Coupling
	11:00:00	Martin Lackner Permutation Pattern Matching and its Parameterized Complexity	Natasha Jonoska and Mile Krajcevski and Gregory McColm Languages Associated with Crystallographic Structures	Pierre Clairambault and Julian Gutierrez and Glynn Winskel Imperfect Information in Logic and Concurrent Games	David Fernández and Joost Joosten Turing Progressions and their well-orders	Liesbeth De Mol and Maarten Bullynck A short history of small machines	Rebecca Steiner Low_n Boolean Subalgebras	Sorin Istrail Computer Science Through Urn Games: A Unified Framework for a Hierarchy of Solvable and Unsolvable Problems
	11:15:00	Rusins Freivalds Ultrametric versus Archimedean automata	Vladimir Aristov and Andrey Stroganov Computing without a computer: the analytical calculus by means of formalizing classical computer operations	Yoshihiro Maruyama Categorical Universal Logic: Duality as Semantics	Ivan Georgiev Complexity of the Continued Fractions of Some Subrecursive Real Numbers	Loizos Michael Simultaneous Learning and Prediction	Chengling Fang and Shenling Wang and Guohua Wu Highness and Local Noncappability	Akitoshi Kawamura and Carsten Rösnick and Martin Ziegler Second-Order Representations and Complexity of Compact Sets
	11:30:00	Jürgen Dassow and Florin Manea and Robert Mercas Connecting Partial Words and Regular Languages	Anders Johansson and James Zou A Slime Mold Solver for Linear Programming Problems	Bastien Le Gloannec and Nicolas Ollinger Substitutions and Strongly Deterministic Tilesets	Bahareh Afshari and Michael Rathjen Ordinal Analysis and the Infinite Ramsey Theorem	Madalina Erascu and Tudor Jebelean Automated Certification of a Logic-Based Verification Method for Imperative Loops	Vasco Brattka and Stéphane Le Roux and Arno Pauly On the Computational Content of the Brouwer Fixed Point Theorem	Mariam Thalos and Oliver Richardson The Morals of the St. Petersburg Game: Why Statistical Distributions Matter in Prospect Appraisal
	11:45:00	Olivier Finkel Ambiguity of $\omega$-Languages of Turing Machines	Benedek Nagy and Veronika Halász and László Hegedüs and István Hornyák Solving application oriented graph theoretical problems with DNA computing	Yiorgos Stavrinos and Anastasia Veneti Linear Aspects of Intersection	Lorenzo Carlucci and Konrad Zdanowski A note on Ramsey Theorems and Turing Jumps	Jiamou Liu An Automata Model for Computations Over an Arbitrary Structure	Robert Rettinger Compactness and the Effectivity of Uniformization	Selmer Bringsjord Naive Unrevealably Secret Communication
	12:00:00	Filip Mazowiecki Continuous reductions of regular languages	Daniela Genova and Kalpana Mahalingam Generating DNA Code Words Using Forbidding and Enforcing Systems	Matthew Wright Degrees of Relations on Ordinals	Anupam Das Complexity of Deep Inference via Atomic Flows	Ilkka Törmä and Ville Salo On Shift Spaces with Algebraic Structure	William Calhoun The Legacy of Turing Reducibility	Michael Olinick An Undergraduate Course on the Life and Work of Alan Turing
	12:15:00	Szilard Zsolt Fazekas and Robert Mercas and Kayoko Shikishima-Tsuji Palindromic completion and a basis for hairpin completion	Jole Costanza and Claudio Angione and Pietro Lio' and Giuseppe Nicosia Are Bacteria Unconventional Computing Architectures?		Stephen Flood Reverse mathematics and a packed Ramsey's theorem.		Sergei Podzorov Computable C-classes	Lindsay Smith and Vito Veneziano and Paul Wernick The use of language and logic in computing technology

		Session 1 (BLT) Chair: Istrail	Session 2 (CLT) Chair: Boas	Session 3 (ASA) Chair: Adriaans	Session 4 (ASB) Chair: Freer	Session 5 (ASC) Chair: Lubarsky	Session 6 (LEH) Chair: Soskova	Session 7 (SS1) Chair: Kristiansen

Fri June 22 afternoon	17:30:00	Krishna S and Bogdan Aman and Gabriel Ciobanu On the Computability Power of Membrane Systems with Controlled Mobility	Shannon Bohle Virtual Worlds as Portals for Information Discovery	Dan Brumleve and Joel David Hamkins and Philipp Schlicht The mate-in-n problem of infinite chess is decidable	Steven Ericsson-Zenith Toward the unification of logic and geometry as the basis of a new computational paradigm	Iosif Petrakis and Helmut Schwichtenberg On the Formal Constructive Theory of Computable Functionals TCF^{+}	Liliana Badillo and Charles Harris 1-genericity and the $\Pi_2$ enumeration degrees	Haroldas Giedra and Jurate Sakalauskaite Sequent calculus with algorithmic properties for logic of correlated knowledge
	17:45:00	Francis George Cabarle and Henry Adorna Notes on Spiking Neural P systems and Petri nets	Martin Adamcik Collective Reasoning under Uncertainty and Inconsistency	Andris Ambainis and Arturs Backurs and Kaspars Balodis and Agnis Skuskovniks and Juris Smotrovs and Madars Virza Worst case analysis of non-local games	Stephane Massonet Turing and Wittgenstein : from the Foundations of Mathematics to Intelligent machines	Kenji Miyamoto and Helmut Schwichtenberg Program Extraction with Nested Inductive/Coinductive Definitions	Chung-Chih Li Is the Trilogy of Gap and Compression and and Honesty Theorems Still Significant at Type-2?	Ralph Wojtowicz and Selmer Bringsjord and John Hummel Dynamic Semantics of Tau-N Theories
	18:00:00	Mike Stannett and Marian Gheorghe and Erzsébet Csuhaj-Varjú Using Topological Spaces to Control P Systems	Aziz F. Zambak Mind as IRIS versus Mind as Machine	Naveen Sundar Govindarajulu Uncomputable Games: Toward Crowd-sourced Solving of Truly Difficult Problems	Stefan Gerdjikov On modernisation of historical texts	Naohi Eguchi and Andreas Weiermann A Simplified Characterisation of Provably Computable Functions of the System ID_1	Aliakbar Safilian and Farzad Didehvar Two New Reducibilities Based on Enumeration Orders	Giuseppe Primiero A verificationist modal language for contextual computations
	18:15:00

		Session 1 (BLT)	Session 2 (CLT)	Session 3 (ASA)	Session 4 (ASB)	Session 5 (ASC)	Session 6 (LEH)	Session 7 (SS1)

Abbreviation	Room
BLT	Babbage Lecture Theatre
CLT	Cockcroft Lecture Theatre
ASA	Arts School Room A
ASB	Arts School Room B
ASC	Arts School Room C
LEH	Large Examination Hall
SS1	Studio Seminar Room 1

local websites: Arno Pauly

2011-12-06