Language, Life, Limits: 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Proceedings

Front Matter....Pages -
Computability and Categoricity of Ultrahomogeneous Structures....Pages 1-10
Parameterized Inapproximability of Target Set Selection and Generalizations....Pages 11-20
How can Grammatical Inference Contribute to Computational Linguistics?....Pages 21-31
Algorithms and Their Explanations....Pages 32-41
Gene Tree Correction by Leaf Removal and Modification: Tractability and Approximability....Pages 42-52
Uniform Schemata for Proof Rules....Pages 53-62
Graph Polynomials Motivated by Gene Rearrangements in Ciliates....Pages 63-72
On the Equivalence of Automata for KAT -expressions....Pages 73-83
Algorithmic Randomness for Infinite Time Register Machines....Pages 84-92
Constraint Logic Programming for Resolution of Relative Time Expressions....Pages 93-102
Maximal Parallelism in Membrane Systems with Generated Membrane Boundaries....Pages 103-112
Learnability Thesis Does Not Entail Church’s Thesis....Pages 113-122
Phase Transitions Related to the Pigeonhole Principle....Pages 123-132
Generic Parallel Algorithms....Pages 133-142
Isomorphisms of Non-Standard Fields and Ash’s Conjecture....Pages 143-152
Modeling Life as Cognitive Info-computation....Pages 153-162
Deciding the Borel Complexity of Regular Tree Languages....Pages 163-172
Chemical Production and Molecular Computing in Addressable Reaction Compartments....Pages 173-182
Visual Modelling of Complex Systems: Towards an Abstract Machine for PORGY....Pages 183-193
Fixed Points and Attractors of Reaction Systems....Pages 194-203
Fit-Preserving Data Refinement of Mass-Action Reaction Networks....Pages 204-213
On Maximal Block Functions of Computable η -like Linear Orderings....Pages 214-223
Lossiness of Communication Channels Modeled by Transducers....Pages 224-233
Predicate Characterizations in the Polynomial-Size Hierarchy....Pages 234-244
Function Spaces for Second-Order Polynomial Time....Pages 245-254
Complexity of Operation Problems....Pages 255-264
A Computational Model of XACML–Based Access Control Management in Distributed Networks....Pages 265-274
Early Machine Translation....Pages 275-282
Lines Missing Every Random Point....Pages 283-292
Natural Descriptions and Anthropic Bias: Extant Problems In Solomonoff Induction....Pages 293-302
An Efficient Algorithm for the Equation Tree Automaton via the k -C-Continuations....Pages 303-313
On the Effectiveness of Symmetry Breaking....Pages 314-323
On the Ramseyan Factorization Theorem....Pages 324-332
The Complexity of Satisfaction Problems in Reverse Mathematics....Pages 333-342
An Early Completion Algorithm: Thue’s 1914 Paper on the Transformation of Symbol Sequences....Pages 343-346
Metric-Driven Grammars and Morphogenesis (Extended Abstract)....Pages 347-351
Hyperprojective Hierarchy of qcb 0 -Spaces....Pages 352-361
Online Bin Packing: Old Algorithms and New Results....Pages 362-372
Pluralism Ignored: The Church-Turing Thesis and Philosophical Practice....Pages 373-382
The FPGA-Based High-Performance Computer RIVYERA for Applications in Bioinformatics....Pages 383-392
Exploiting Membrane Features to Compute....Pages 393-402
Short Lists with Short Programs in Short Time – A Short Proof....Pages 403-408
Back Matter....Pages -