CiE 2012 - How the World Computes

Print current page  Print this page


Schedule of Contributed Talks

Back to overview schedule
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
June 19
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:00Stefano 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:00Sebastian 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:00Russell 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:00Magnus 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:00Marcin 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
June 19
17:30:00Anargyros 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:00Alison 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:00Ashish 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:00Sabine 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
June 20
10:30:00David 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:00Yun 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:00Luí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:00Sylvain 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
June 21
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
June 22
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:00Martin 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:00Rusins 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:00Olivier 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:00Filip 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:00Szilard 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
June 22
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:00Francis 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:00Mike 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
Session 1 (BLT) Session 2 (CLT) Session 3 (ASA) Session 4 (ASB) Session 5 (ASC) Session 6 (LEH) Session 7 (SS1)
BLTBabbage Lecture Theatre
CLTCockcroft Lecture Theatre
ASAArts School Room A
ASBArts School Room B
ASCArts School Room C
LEHLarge Examination Hall
SS1Studio Seminar Room 1

The Alan Turing Year ASL Cambridge University Cambridge University Press Computability in Europe the source site ELsevier EACSL EATCS IET IFCoLog IOS Press Isaac Newton Institute King's College, Cambridge Microsoft Research Cambridge Science AAAS Springer

local websites: Arno Pauly 2011-12-06 Valid HTML 4.01! Valid CSS!