Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Accepted Papers

The following papers have been accepted for presentation at CiE 2008. Some of these papers (indicated by LNCS logo) have been accepted for publication in the pre-proceedings volume published in the Lecture Notes in Computer Science volume 5028, the others will be published in our abstract booklet. All authors of papers presented at CiE 2008 may be invited to submit papers to one of the post-conference publications.

Author Title
Grazyna Zwozniak Induced matchings in graphs of maximum degree three
Keita Yokoyama Reverse Mathematics for Fourier Expansion
LNCS logo Guohua Wu and Jiang Liu Joining to High Degrees
Joost Winter Space Complexity in Ordinal Turing Machines
Michael Weiss and Gregory Lafitte Simulations Between Tilings
LNCS logo Daniel Ventura, Mauricio Ayala-Rincon and Fairouz Kamareddine Principal Typings for Explicit Substitutions Calculi
Alina Vasilieva Quantum Query Algorithms for AND and OR Boolean Functions
LNCS logo Guillaume Theyssier and Mathieu Sablik Topological Dynamics of 2D Cellular Automata
Hayato Takahashi and Kazuyuki Aihara Probabilistic machines vs. relativized computation
Ákos Tajti and Benedek Nagy Solving Tripartite Matching by Interval-valued Computation in Polynomial Time
Kohtaro Tadaki A statistical mechanical interpretation of algorithmic information theory
LNCS logo Mariya Ivanova Soskova Cupping Classes of Sigma 2 Enumeration Degrees
LNCS logo Alexandra Soskova Omega Degree Spectra
Michael Soltys and Craig Wilson On the complexity of computing winning strategies for finite poset games
Boris Solon Almost partial m-reducibility
LNCS logo Victor Selivanov and Klaus W. Wagner Complexity of aperiodicity for topological properties of regular $\omega$-languages
Zenon Sadowski Optimal proof systems and complete languages
LNCS logo Krishna S, Lakshmi Manasa G and Kumar Nagaraj Updatable Timed Automata with Additive and Diagonal Constraints
LNCS logo Krishna S and Gabriel Ciobanu On the Computational Power of Enhanced Mobile Membranes
LNCS logo Vladimir Rybakov and Sergei Babyonyshev Decidability of Hybrid Logic with Local Common Knowledge based on Linear Temporal Logic LTL
Alexandra Revenko Autostability of Automatic Linear Orders
Daowen Qiu Simulations of Quantum Turing Machines by Quantum Multi-Counter Machines
Mihai Prunescu Polynomial iterations over finite fields
Petrus H. Potgieter Computable counter-examples to the Brouwer fixed-point theorem
LNCS logo Sergei Podzorov Upper Semilattices in Many-One Degrees
Yongri Piao, Seoktae Kim and Sung-Jin Cho Two-Dimensional Cellular Automata Transforms for a Novel Edge Detection
Florian Pelupessy and Andreas Weiermann Classifying the phase transition threshold for unordered regressive Ramsey numbers
LNCS logo Nicolas Ollinger Two-by-two Substitution Systems and the Undecidability of the Domino Problem
Vivek Nigam Using Tables to Construct Non-Redundant Proofs
LNCS logo Takako Nemoto Complete Determinacy and Subsystems of Second Order Arithmetic
Marcin Mostowski Limiting recursion, FM--repressentability, and hypercomputations
LNCS logo Russell Miller and Dustin Mulcahey Perfect Local Computability and Computable Simulations
LNCS logo Barnaby Martin First-Order Model Checking Problems Parameterized by the Model
Angelos Manousaridis, Michalis Papakyriakou and Nikolaos Papaspyrou From Program Verification to Certified Binaries
Johann Makowsky From Hilbert's Program to a Logic Toolbox
LNCS logo Iris Loeb Factoring out Intuitionistic Theorems: Continuity Principles and the Uniform Continuity Theorem
Chung-Chih Li Query-Optimal Oracle Turing Machines for Type-2 Computations
Maikel Leon, Isis Bonet and Zenaida Garcia Combining Concept Maps and Petri Nets to Generate Intelligent Tutoring Systems
Stephane Le Roux Discrete Non Determinism and Nash Equilibria for Strategy-Based Games
LNCS logo James Lathrop, Jack H. Lutz, Matthew J. Patitz and Scott M. Summers Computability and Complexity in Self-Assembly
Sunil Kothari and James Caldwell On Extending Wand's Type Reconstruction Algorithm to Handle Polymorphic Let
Margarita Korovina and Nicolai Vorobjov Safety Properties Verification for Pfaffian Dynamics
LNCS logo Peter Koepke and Russell Miller An Enhanced Theory of Infinite Time Register Machines
LNCS logo Bakhadyr Khoussainov, Michael Brough and Peter Nelson Sequential Automatic Algebras
Basil A. Karadais A Plotkin Definability Theorem for Atomic-Coherent Information Systems
LNCS logo Temesghen Kahsai and Marino Miculan Implementing Spi Calculus using Nominal techniques
Reinhard Kahle Towards Reverse Proofs-as-Programs
Herman Ruge Jervell Ordering finite labeled trees
ilyes jenhani, Zied Elouedi and Salem Benferhat The Use of Information Affinity in Possibilistic Decision Tree Learning and Evaluation
Maurice Jansen A Non-Linear Lower Bound for Syntactically Multilinear Algebraic Branching Programs
Sanjay Jain, Frank Stephan and Nan Ye Prescribed Learning of Indexed Families
LNCS logo Gabriel Istrate, Madhav Marathe and S. S. Ravi Adversarial Scheduling Analysis of Game-Theoretic Models of Norm Diffusion
Bernhard Irrgang and Benjamin Seyfferth Multitape Ordinal Machines and Primitive Recursion
Yoon-Hee Hwang, Sung-Jin Cho, Un-Sook Choi and Han-Doo Kim Modelling Linear Cellular Automata with the minimum stage corresponding to CCSG based on LFSR
Yoshihiro Horihata and Keita Yokoyama Singularities of Holomorphic Functions in Subsystems of Second Order Arithmetic
LNCS logo Mircea-Dan Hernest and Paulo Oliva Hybrid Functional Interpretations
LNCS logo Emmanuel Hainry Reachability in linear dynamical systems
LNCS logo Xiaoyang Gu and Jack H. Lutz Effective Dimensions and Relative Frequencies
LNCS logo Rica Gonen On the Hardness of Truthful Online Auctions with Multidimensional Constraints
LNCS logo Christian Glaßer, Christian Reitwießner and Victor Selivanov The Shrinking Property for NP and coNP
Alexander Gavryushkin Computable Models Spectras of Ehrenfeucht Theories
Christine Gaßner Computation over Groups
André Luiz Galdino and Mauricio Ayala-Rincon Verification of Newman's and Yokouchi's Lemmas in PVS
LNCS logo willem fouche Subrecursive complexity of identifying the Ramsey structure of posets
Ekaterina Fokina Algorithmic Properties of Structures for Languages with Two Unary Functional Symbols
Pantelis Eleftheriou, Costas Koutras and Christos Nomikos Notions of Bisimulation for Heyting-Valued Modal Languages
Jérôme Durand-Lose Abstract geometrical computation: beyond the Blum, Shub and Smale model with accumulation
LNCS logo Jacques Duparc and Alessandro Facchini Describing the Wadge Hierarchy for the Alternation Free Fragment of $\mu$-Calculus (I): The Levels Below $\omega_{1}$
LNCS logo Giovanni Di Crescenzo and Helger Lipmaa Succinct NP Proofs from an Extractable-Algorithm Assumption
LNCS logo Michiel De Smet and Andreas Weiermann Phase transitions for weakly increasing sequences, the Erdös-Szekeres theorem and the Dilworth theorem
LNCS logo Liesbeth De Mol and Maarten Bullynck A week-end off. The first extensive number-theoretical computation on the ENIAC.
Gregorio de Miguel Casado, Juan Manuel García-Chamizo and Higinio Mora Mora Online-division with Periodic Rational Numbers
LNCS logo Barbara Csima, Jiamou Liu and Bakhadyr Khoussainov Computable Categoricity of Graphs with Finite Components
Antonio Carlos Costa and Graçaliz Dimuro Introducing Service Schemes and Systems Organization in the Theory of Interactive Computation
LNCS logo Charalampos Cornaros Pell equations and weak regularity priciples
Sung-Jin Cho, Un-Sook Choi, Han-Doo Kim, Yoon-Hee Hwang and Jin-Gyoung Kim Phase shifts of LFSM as pseudorandom number generators for BIST for VLSI
Luca Chiarabini Extraction of Efficient Programs from Correct Proofs: The Case of Structural Induction over Natural Numbers
William Calhoun Triviality and Minimality in the Degrees of Monotone Complexity
LNCS logo Jérémie Cabessa and Jacques Duparc The Algebraic Counterpart of the Wagner Hierarchy
LNCS logo Amir Ben-Amram, Lars Kristiansen and Neil Jones Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
Edwin Beggs and Annelies Gerber Algorithms for Analytic Functions and Applications to Toeplitz Operators
LNCS logo Mathias Barra Pure iteration and periodicity
LNCS logo George Metcalfe and Matthias Baaz Herbrand Theorems and Skolemization for Prenex Fuzzy Logics
Tiago Azevedo, Mario Benevides, Fabio Protti and Marcelo Sihman On detecting deadlock in the Pi-Calculus
LNCS logo Argimiro Arratia and Iain Stewart Program schemes with deep pushdown storage
Luis Antunes and André Souto Sophisticated Infinite Sequences
Bogdan Aman and Gabriel Ciobanu Decidability Results for Mobile Membranes derived from Mobile Ambients
Marco Almeida, Nelma Moreira and Rogério Reis On the performance of automata minimization algorithms

websites: Arnold Beckmann 2008-05-22 Valid HTML 4.01! Valid CSS!