Language, Life, Limits

1. Front Matter

   PDF

2. Computability and Categoricity of Ultrahomogeneous Structures

   • Francis Adams, Douglas Cenzer

   Pages 1-10

3. Parameterized Inapproximability of Target Set Selection and Generalizations

   • Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora

   Pages 11-20

4. How can Grammatical Inference Contribute to Computational Linguistics?

   • Leonor Becerra-Bonache

   Pages 21-31

5. Algorithms and Their Explanations

   • Marco Benini, Federico Gobbo

   Pages 32-41

6. Gene Tree Correction by Leaf Removal and Modification: Tractability and Approximability

   • Stefano Beretta, Riccardo Dondi

   Pages 42-52

7. Uniform Schemata for Proof Rules

   • Ulrich Berger, Tie Hou

   Pages 53-62

8. Graph Polynomials Motivated by Gene Rearrangements in Ciliates

   • Robert Brijder, Hendrik Jan Hoogeboom

   Pages 63-72

9. On the Equivalence of Automata for KAT-expressions

   • Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis

   Pages 73-83

10. Algorithmic Randomness for Infinite Time Register Machines

    • Merlin Carl

    Pages 84-92

11. Constraint Logic Programming for Resolution of Relative Time Expressions

    • Henning Christiansen

    Pages 93-102

12. Maximal Parallelism in Membrane Systems with Generated Membrane Boundaries

    • Zoltán Ernő Csajbók, Tamás Mihálydeák

    Pages 103-112

13. Learnability Thesis Does Not Entail Church’s Thesis

    • Marek Czarnecki, Michał Tomasz Godziszewski, Dariusz Kalociński

    Pages 113-122

14. Phase Transitions Related to the Pigeonhole Principle

    • Michiel De Smet, Andreas Weiermann

    Pages 123-132

15. Generic Parallel Algorithms

    • Nachum Dershowitz, Evgenia Falkovich

    Pages 133-142

16. Isomorphisms of Non-Standard Fields and Ash’s Conjecture

    • Rumen Dimitrov, Valentina Harizanov, Russell Miller, K. J. Mourad

    Pages 143-152

17. Modeling Life as Cognitive Info-computation

    • Gordana Dodig-Crnkovic

    Pages 153-162

18. Deciding the Borel Complexity of Regular Tree Languages

    • Alessandro Facchini, Henryk Michalewski

    Pages 163-172

19. Chemical Production and Molecular Computing in Addressable Reaction Compartments

    • Harold Fellermann, Natalio Krasnogor

    Pages 173-182

20. Visual Modelling of Complex Systems: Towards an Abstract Machine for PORGY

    • Maribel Fernández, Hélène Kirchner, Ian Mackie, Bruno Pinaud

    Pages 183-193

This book constitutes the refereed proceedings of the 10th Conference on Computability in Europe, CiE 2014, held in Budapest, Hungary, in June 2014. The 42 revised papers presented were carefully reviewed and selected from 78 submissions and included together with 15 invited papers in this proceedings. The conference had six special sessions: computational linguistics, bio-inspired computation, history and philosophy of computing, computability theory, online algorithms and complexity in automata theory.

• algorithms
• automata theory
• bio-inspired computation
• biological computing
• computability theory
• computational complexity
• computational linguistics
• history of computing
• natural computing
• online algorithms
• theory of computation
• algorithm analysis and problem complexity

• College of Science, Department of Computer Science, Swansea University, Swansea, UK

  Arnold Beckmann

• Department of Algorithms and Their Applications, Eötvös Loránd University, Budapest, Hungary

  Erzsébet Csuhaj-Varjú

• Computer Science Institute, Brandenburg University of Technology Cottbus-Senftenberg, Cottbus, Germany

  Klaus Meer

Policies and ethics