torre CiE 2007 logo
CiE 2007 | General Information | Participation | Scientific Programme | Publications | CiE | CCA 2007
photo credit
Contributed Talks

Luigi Acerbi, Alberto Dennunzio and Enrico Formenti
Shifting and Lifting of Cellular Automata

Bahareh Afshari
Information Content and Computability in the n-C.E. Hierarchy II

Yohji Akama
Omega-Rules and Learnability

Sandra Alves, Maribel Fernandez, Mario Florido and Ian Mackie
Very Primitive Recursive Functions

Bogdan Aman and Gabriel Ciobanu
Mobile Ambients and Mobile Membranes

Maxime Amblard and Christian Retore
Natural Deduction and Normalisation for Partially Commutative Linear Calculi Used in Concurrency Theory and Computational Linguistic

Luis Antunes, Armindo Costa, Armando Matos and Paul Vitanyi
Computational Depth of Infinite Strings Revisited

Kostyantyn Archangelsky
A New Approach to the Uncounting Problem for Regular Languages

Ofer Arieli
Paraconsistent Reasoning and Distance Minimization

Argimiro Arratia and Carlos Ortiz
Syntactic Approximations to Computational Complexity Classes

Fatih Basciftci
Exact Direct Cover Minimization Algorithm for a Single Output of Switching Functions

Mathias Barra, Lars Kristiansen and Paul Voda
Nondeterminism Without Turing Machines

Josef Berger
Weak Koenig's Lemma Implies the Fan Theorem for c-bars

Francesco Bernardini, Marian Gheorghe, Maurice Margenstern and Sergey Verlan
Producer/Consumer in Membrane Systems and Petri Nets

Olaf Beyersdorff
The Deduction Theorem, Optimal Proof Systems, and Complete Disjoint NP-Pairs

Rongfang Bie and Guohua Wu
A Minimal Pair in the Quotient Structure M/NCup

Laurent Bienvenu, Wolfgang Merkle and Alexander Shen
Some Results and Questions in Effective Measure Theory

Laurent Bienvenu, David Doty and Frank Stephan
Constructive Dimension and Weak Truth-Table Degrees

Jens Blanck
Framework for Comparing Domain Representations

Guillaume Bonfante, Matthieu Kaczmarek and Jean-Yves Marion
Classification of Viruses through Recursion Theorems

Alexandre Borovik and Şükrü Yalçinkaya
Black Box Groups: Guesswork, Computation, Proof

Vasco Brattka and Guido Gherardi
Borel Complexity of Topological Operations on Computable Metric Spaces

Nadia Busi and Claudio Zandron
Computing with Genetic Gates

Gregorio de Miguel Casado, Juan Manuel Garcia and Maria Teresa Signes Pont
Algebraic Model of an Arithmetic Unit for TTE-Computable Normalized Rational Numbers

John Case and Samuel Moelius
Characterizing Programming Systems Allowing Program Self-Reference

Douglas Cenzer, George Barmpalias, Jeffrey Remmel and Rebecca Weber
K-trivial Closed Sets and Continuous Functions

Douglas Cenzer, Geoffrey LaForte and Guohua Wu
Pseudojump Operators and Π01 Classes

Julien Cervelle, Enrico Formenti and Pierre Guillon
Sofic Trace Subshift of a Cellular Automaton

Maria Luisa Dalla Chiara, Roberto Giuntini and Roberto Leporini
Concrete and Abstract Quantum Computational Logics

Yixiang Chen and Hengyang Wu
Semantics of Sub-Probabilistic Programs

Sung-Jin Cho, Un-Sook Choi, Han-Doo Kim, Yoon-Hee Hwang and Jin-Gyoung Kim
Pseudorandom Number Generation Based on 90/150 Linear Nongroup Cellular Automata

Jennifer Chubb, John Chisholm, Valentina S. Harizanov, Denis Hirschfeldt, Carl G. Jockusch, Jr., Timothy McNicholl, and Sarah Pingrey
Strong Degree Spectra of Initial Segments of Scattered Linear Orders

Pieter Collins
Computability of the Evolution of Hybrid Dynamical Systems

Andres Cordon-Franco, Alejandro Fernandez-Margarit and Francisco Felix Lara-Martin
On Rules and Parameter Free Systems in Bounded Arithmetic

Fredrik Dahlgren
Effective Structure Theorems for Spaces of Compactly Supported Distributions

Adrien Revault d'Allonnes, Herman Akdag and Olivier Poirel
Trust-moderated Information-likelihood. A Multi-valued Logics Approach

Norman Danner and James Royer
Time-complexity Semantics for Feasible Affine Recursions (extended abstract)

Stefan Dantchev
Towards a Logical Characterisation of and Complexity Gap Theorems for Resolution-based Propositional Proof Systems

Barnaby Dawson
Alpha Recursion and Ordinal Time Turing Machines

Liesbeth De Mol
Generating Number Sequences Through Periodic Structures in Tag Systems

Ellie D'Hondt
About Quantum Graph Colouring

Graçaliz Dimuro and Antonio Carlos Costa
Towards a Domain-theoretic Model of Developmental Machines

Karim Djemame, Iain Gourlay and James Padgett
Risk-Aware Grid Resource Brokering

Sebastian Dörn
Quantum Algorithms for Graph Traversals and Related Problems

David Doty and Philippe Moser
Feasible Depth

Antonino Drago
Four Ways of Logical Arguing in Theoretical Physics

Jerome Durand-Lose
Abstract Geometrical Computation and Linear BSS

Olivier Finkel and Dominique Lecomte
There Exist Some ω-Powers of Any Borel Rank

Ekaterina Fokina
Decidable Theories of Computable Structures

Giuditta Franco
Membrane Dynamical Systems: Open Problems

Josep Freixas, Xavier Molinero and Salvador Roura
Minimal Representations for Majority Games

Joel Friedman
Linear Transformations in Boolean Complexity Theory

Stefano Galatolo
Computable Measures and Dynamical Systems

Nicola Galesi and Massimo Lauria
Complexity of Proofs in Extensions of the Polynomial Calculus

Hristo Ganchev
Exact Pair Theorem for the ω-Enumeration Degrees

Ying Gao and Jingde Cheng
Operational Semantics for Positive Relevant Logics without Distribution

Christine Gaßner
P = NP for Expansions Derived from Some Oracles

Raffaella Gentilini, Bud Mishra, and Klaus Schneider
Automated Abstraction-Refinement of Hybrid Automata for Monotonic CTL Model Checking

Annelies Gerber
Resolution Proofs Hidden in Mathematical and Physical Structures and Complexity

Giangiacomo Gerla
Multi-valued Logics, Effectiveness and Domains

Guido Gherardi
Internal Computability

Sujata Ghosh, Benedikt Löwe, Erik Scorelle, and Fernando Velazquez-Quernada
Belief Flow Networks

Luis Mendes Gomes and Jose Felix Costa
Hybrid Finite Computation

Sergey S. Goncharov
Classification Problems for Computable Structures

Ferruccio Guidi
Lambda Types on the Lambda Calculus with Abbreviations

Joel David Hamkins and Russell Miller
Post's Problem for Ordinal Register Machines

Peter Hancock
Continuous Stream Processing and a Generalisation

Eiju Hirowatari, Kouichi Hirata and Tetsuhiro Miyahara
Learnability of Recursively Enumerable Sets of Recursive Real-Valued Functions

Robin Hirsch and Evan Tzanis
A Logic for Probabilistic XML Documents with Applications to Updates

Tseren-Onolt Ishdorj, Ion Petre and Vladimir Rogojin
Computational Power of Intramolecular Gene Assembly

Iraj Kalantari and Larry Welch
On Turing Degrees of Points in Computable Topology

Iskander Kalimullin
Some Notes on Degree Spectra of the Structures

Kentaro Kikuchi
Confluence of Cut-Elimination Procedures for the Intuitionistic Sequent Calculus

Peter Koepke and Benjamin Seyfferth
Doing α-Recursion Theory with Ordinal Machines

Margarita Korovina and Oleg Kudinov
The Uniformity Principle for Σ-definability with Applications to Computable Analysis

S. N. Krishna
On the Computational Power of Flip-Flop Proteins on Membranes

Oleg Kudinov and Victor Selivanov
Definability in the Homomorphic Quasiorder of Finite Labeled Forests

Gregory Lafitte and Christophe Papazian
The Fabric of Small Turing Machines

James Lathrop, Jack H. Lutz and Scott M. Summers
Strict Self-Assembly of Discrete Sierpinski Triangles

Gyesik Lee
Binary Trees and (Maximal) Order Types

Domenico Lenzi
On a Constructive Proof of Completeness of Positive Implicational Propositional Calculus

Stéfane Le Roux
Acyclicity of Preferences, Nash Equilibria, and Subgame Perfect Equilibria: a Formal and Constructive Equivalence

Andrew Lewis, Antonio Montalban and Andre Nies
A Weakly 2-Random Set that is not Generalized Low

Chung-Chih Li
Speed-up Theorems in Type-2 Computation

Zhimin Li, Libo Lo and Xiang Li
On the Computational Complexity of the Theory of Complete Binary Trees

Chih-Hao Lin and Jiun-De He
A Multiple-Evaluation Genetic Algorithm for Numerical Optimization Problems

David Linetsky, Joel David Hamkins and Russell Miller
The Complexity of Quickly Decidable ORM Sets

Bruno Loff
A Functional Characterisation of the Analytical Hierarchy

Remco Loos
On Accepting Networks of Splicing Processors of Size 3

Carlos Lourenço
How Can Natural Brains Help Us Compute?

Mashudu Makananise and Vasco Brattka
Limit Computable Functions

Florin Manea and Victor Mitrana
Hairpin Completion Versus Hairpin Reduction

Bruno Marchal
A Purely Arithmetical, yet Empirically Falsifiable, Interpretation of Plotinus' Theory of Matter

Alberto Marcone
The Strength of Fraïssé's Conjecture for Finite Hausdorff Rank

Barnaby Martin and Florent Madelaine
Hierarchies in Fragments of Monadic Strict NP

Armando Matos, Andreia Teixeira and Andre Souto
Non-deterministic Communication Complexity and Instance Complexity

Alexander Melnikov
Enumerations and Torsion Free Abelian Groups

Joseph S. Miller
Weak Lowness Properties and Randomness

Russell Miller
Locally Computable Structures

Mia Minnes and Bakhadyr Khoussainov
Solution to a Problem of Vardi on Ordinal Heights of Well-founded Automatic Relations

Anthony Morphett and George Barmpalias
Almost-Everywhere Domination, Non-cupping and LR-reducibility

Benedek Nagy and Remco Loos
Parallelism in DNA and Membrane Computing

Elzbieta Nowicka and Marcin Zawada
On the Complexity of Matching Non-injective General Episodes

Adam Obtulowicz
Multigraph Membrane Systems: a Visual Formalism for Modeling Complex Systems in Biology and Evolving Neural Networks

Kerry Ojakian
Some New Approaches to Characterizing Computable Analysis by Analog Computation

Martin Olsen
Nash Stability in Additively Separable Hedonic Games is NP-hard

Juan Ospina and Mario Velez
Universal Quantum Computation via Yang-Baxterization of the Two-colour Birman-Wenzl-Murakami Algebra

Marco Pedicini and Mario Piazza
Elementary Complexity into the Hyperfinite II1 Factor

Alexandre Pinto
Comparing Notions of Computational Entropy

Sergei Podzorov
On Isomorphism Type of Some Structures in Many-One Degrees

Oriana Ponta
A Fixed-Parameter Approach to the Convex Recoloring Problem

Mihai Prunescu
Self-similar Carpets Associated with the Odd Primes

Paula Quinon and Konrad Zdanowski
The Intended Model of Arithmetic. An Argument from Tennenbaum's Theorem

Mark Rhodes
Rank Lower Bounds for the Sherali-Adams Operator

Frances A. Rosamond and Michael Fellows
The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number

Frances A. Rosamond and Michael Fellows
Why is P Not Equal to NP?

Branislav Rovan and Lubos Steskal
Infinite Computations and a Hierarchy in Δ3

Sam Sanders, Chris Impens and Andreas Weiermann
What If Computers Could Count To Infinity?

Jose Espirito Santo
Refocusing Generalised Normalisation

Peter Schuster
Problems as Solutions

Victor Selivanov
A Useful Undecidable Theory

Alla Sirokofskich
Counting, Collection and the Weak Pigeon-hole Principle

Zvonimir Šikić
Gödel's Incompleteness Theorem and Man-Machine Non-equivalence

Boris Solon
Co-total Enumeration Degrees. Part 2

Ivan Soskov
The Jump Operator on the ω-Enumeration Degrees

Alexandra Soskova
A Jump Inversion Theorem for the Degree Spectra

Mariya Ivanova Soskova
A Non-splitting Theorem in the Enumeration Degrees

Mariya Ivanova Soskova and Guohua Wu
Cupping Δ2 Enumeration Degrees to 0e'

Iain Stewart
Logically Capturing Complexity Classes Within the Polynomial Hierarchy

Alexey Stukachev
Effective Reducibilities on Structures and Degrees of Presentability

Zhuldyz Talasbayeva
On Computability in Ershov's Hierarchy

Mingji Xia
Universal Match Gates

Fan Yun , Decheng Ding and Xizhong Zheng
Totally d-c.e. Real Numbers

Peng Zhang
Approximating Generalized Multicut on Trees

Paola Anna Zizzi
Turning the Liar Paradox into a Metatheorem of Basic Logic

Maxim Zubkov
On η-Representable Sets

= accepted paper  = informal presentation

palazzo publico

CiE logo
EATCS logo ASL logo AILA logo
EACSL logo LNCS logo FoLLI logo CRA-W logo MPS logo
CiE logo CiE 2005 small poster CiE 2006 small poster CiE07 poster CCA logo UNISI logo GNSAGA Springer
B. Cooper
Valid HTML 4.01!