FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 |

«Logic and Theory of Algorithms Fourth Conference on Computability in Europe, CiE 2008 Local Proceedings June 15–20, 2008 University of Athens ...»

-- [ Page 1 ] --

Arnold Beckmann

Costas Dimitracopoulos

Benedikt L¨ we (Editors)


Logic and Theory of Algorithms

Fourth Conference on Computability in Europe, CiE 2008

Local Proceedings

June 15–20, 2008 University of Athens


CiE 2008: Logic and Theory of Algorithms

Athens, Greece, June 15–20, 2008

Computability in Europe (CiE) is an informal network of European scientists

working on computability theory, including its foundations, technical development, and applications. Among the aims of the network is to advance our theoretical understanding of what can and cannot be computed, by any means of computation. Its scientific vision is broad: computations may be performed with discrete or continuous data by all kinds of algorithms, programs, and machines. Computations may be made by experimenting with any sort of physical system obeying the laws of a physical theory such as Newtonian mechanics, quantum theory, or relativity. Computations may be very general, depending on the foundations of set theory; or very specific, using the combinatorics of finite structures. CiE also works on subjects intimately related to computation, especially theories of data and information, and methods for formal reasoning about computations. The sources of new ideas and methods include practical developments in areas such as neural networks, quantum computation, natural computation, molecular computation, computational learning. Applications are everywhere, especially, in algebra, analysis and geometry, or data types and programming. Within CiE there is general recognition of the underlying relevance of computability to physics and a broad range of other sciences, providing as it does a basic analysis of the causal structure of dynamical systems.

The conference was based on invited tutorials and lectures, a set of special sessions on a range of subjects as well as contributed papers and informal presentations. The formal proceedings volume appeared in the Springer LNCS series, Vol. 5028 and contains 25 of the invited lectures and 36 of the submitted contributed papers. The present volume represents the informal


booklet which contains another 86 of the contributed talks and two invited plenary talks as well as 23 abstracts of informal presentations. The informal abstract booklet is not a scholarly publication, and papers appearing in it should not be considered published or as selected in a peer review process. There will be a number of post-proceedings publications, including special issues of Theory of Computing Systems, Archive for Mathematical Logic, and Journal of Algorithms.

VI The first three meetings of CiE were at the University of Amsterdam in 2005, at the University of Wales Swansea in 2006, and at the University of Siena in 2007. The large number of mathematicians and computer scientists attending these conference had their view of computability theory enlarged and transformed: they discovered that its foundations were deeper and more mysterious, its technical development more vigorous, its applications wider and more challenging than they had known. The Athens meeting promised to extend and enrich that process.

The annual CiE conference, based on the Computability in Europe network, has become a major event, and is the largest international meeting focused on computability theoretic issues. The series is coordinated by the CiE Conference

Series Steering Committee:

–  –  –

Organization and Acknowledgements The conference CiE 2008 was organized by: Dionysis Anapolitanos (Athens), Arnold Beckmann (Swansea), Costas Dimitracopoulos (Athens, Chair), Michael Mytilinaios (Athens) †, Thanases Pheidas (Heraklion), Stathis Zachos (Athens and New York NY).

The Programme Committee was chaired by Arnold Beckmann and Costas


–  –  –

We are delighted to acknowledge and thank the following for their essential financial support: City of Athens, Bank of Greece, Graduate Program in Logic, Algorithms and Computation (MPLA), Hellenic Ministry of Education, John S.

Latsis Foundation, Kleos S.A., National and Kapodistrian University of Athens, Public Power Corporation S.A., Rizareio Foundation, The Elsevier Foundation.

The high scientic quality of the conference was possible through the conscientious work of the Programme Committee, and the special session organizers.

While papers in this abstract booklet are not to be considered publications, some of the papers in this volume greatly benefitted from comments of the referees during our reviewing process, and we would like to thank the referees for their work. The list of referees is given on pp. IX - X of the mentioned LNCS volume for this conference.

We thank Andrej Voronkov for his EasyChair system which facilitated the work of the Programme Committee and the editors considerably. We also thank Nikolaos S. Papaspyrou for his great support in producing this abstract booklet.

–  –  –

Abstract Geometrical Computation with Accumulations: Beyond the Blum, Shub and Smale model...................................... 107 J´rˆme Durand-Lose eo Notions of Bisimulation for Heyting-Valued Modal Languages.......... 117 Pantelis Eleftheriou, Costas Koutras, Christos Nomikos

–  –  –

Modelling Linear Cellular Automata with the Minimum Stage Corresponding to CCSG based on LFSR............................. 165 Yoon-Hee Hwang, Sung-Jin Cho, Un-Sook Choi, Han-Doo Kim Multitape Ordinal Machines and Primitive Recursion.................. 175 Bernhard Irrgang, Benjamin Seyfferth

–  –  –

Lower Bounds for Syntactically Multilinear Algebraic Branching Programs 195 Maurice Jansen The Use of Information Affinity in Possibilistic Decision Tree Learning and Evaluation................................................... 205 Ilyes Jenhani, Salem Benferhat, Zied Elouedi

–  –  –

Plotkin Definability Theorem for Atomic-Coherent Information Systems. 234 Basil Kar´dais a Safety Properties Verification for Pfaffian Dynamics................... 246 Margarita Korovina, Nicolai Vorobjov X

–  –  –

From Program Verification to Certified Binaries....................... 324 Angelos Manousaridis, Michalis Papakyriakou, Nikolaos Papaspyrou Limiting Recursion, FM–Repressentability, and Hypercomputations..... 332 Marcin Mostowski Using Tables to Construct Non-Redundant Proofs..................... 344 Vivek Nigam Classifying the Phase Transition Threshold for Unordered Regressive Ramsey Numbers................................................. 354 Florian Pelupessy, Andreas Weiermann

–  –  –

Simulations of Quantum Turing Machines by Quantum Multi-Counter Machines........................................................ 397 Daowen Qiu You are reading a preview. Would you like to access the full-text?

–  –  –

The class of automatic structures is the easiest class of computable structures from an algorithmic point of view.

Our investigations concern the problem of existence a computable isomorphism between two automatic presentations of a structure. We say that a structure is autostable under automatic presentations if there is a computable isomorphism between any two automatic presentations of this structure [1]. Here we deal with linear orders.

Some description of automatic linear orders was found by B. Khoussainov, S. Rubin and others. Let L = (L, ≤) be a countable linear order. We say that two elements x, y ∈ L are equivalent if there is a finite number of elements between x and y. The quotient structure with respect to this equivalence relation is a linear order L1 (ordering is induced from the original structure). One can continue this procedure by transfinite induction. So the least ordinal α for which Lα = Lα+1 is a F C-rank of L. Then the F C-rank of automatic linear order is finite [2].

It was earlier showed that all automatic ordinals and automatic scattered linear orders with FC-rank less than 3 are autostable under automatic presentations. We proved that moreover there exist an algorithm which, given two automatic presentations of a scattered linear order with FC-rank less than 3, constructs the computable isomorphism between them. Then every two automatic presentations of scattered linear order with F C-rank 3 are computable isomorphic.


1. Ershov, Yu. L., Goncharov, S. S., Constructive Models, Siberian School of Algebra and Logic, 1999.

2. S. Rubin. Automatic Structures. A thesis submitted in partial fulfilment of the requirements for the Degree of Doctor of Philosophy. The University of Auckland, 2004.

The work was partially supported by President Grant – 335.2008.1 Quantifiers on Automatic Structures

–  –  –

An automatic structure is one that has a presentation consisting of finite or infinite words or trees so that the coded domain and atomic operations are computable by finite automata operating synchronously on their inputs [KN95] [Blu99]. The fundamental fact about these structures is that they are effectively closed under first-order interpretations [BG00]. This result has been strengthened by extending first-order logic with certain generalised quantifiers (for instance, ‘there exist infinitely many’ and ‘there exist k modulo m many’) [BG00] [KRS04] [Col04] [KL05] [BKR07] [BKR08] [KL08].

Say that a generalised quantifier Q preserves regularity for a class of automatic structures C if C is closed under FO + Q interpretations. In this talk I will present some steps towards a fuller understanding of these quantifiers.

I will introduce a natural collection Q of quantifiers, each preserving regularity for the finite-word automatic structures Cfw. The collection Q includes the known quantifiers that preserve regularity for Cfw ; and every unary quantifier that preserves regularity for Cfw is in Q.

This is part of ongoing work with Valentin Goranko and Moshe Vardi.

References [BG00] A. Blumensath and E. Gr¨del. Automatic structures. In 15th Symposium on a Logic in Computer Science (LICS), pages 51–62, 2000.

[BKR07] V. B´r´ny, L. Kaiser, and A. Rabinovitch. Eliminating cardinality quantifiers aa from MLO, 2007. manuscript.

[BKR08] V. B´r´ny, L. Kaiser, and S. Rubin. Cardinality and counting quantifiers on aa omega-automatic structures. In STACS ’08: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008.

[Blu99] A. Blumensath. Automatic Structures. Diploma thesis, RWTH Aachen, 1999.

[Col04] T. Colcombet. Properties and representation of infinite structures. PhD thesis, University of Rennes I, 2004.

[KL05] D. Kuske and M. Lohrey. First-order and counting theories of omegaautomatic structures. Technical Report Fakult¨tsbericht Nr. 2005/07, Univera sit¨t Stuttgart, Fakult¨t Informatik, Elektrotechnik und Informationstechnik, a a 2005.

[KL08] D. Kuske and M. Lohrey. Hamiltonicity of automatic graphs. FIP TCS 2008, 2008.

[KN95] B. Khoussainov and A. Nerode. Automatic presentations of structures. Lecture Notes in Computer Science, 960:367–392, 1995.

[KRS04] B. Khoussainov, S. Rubin, and F. Stephan. Definability and regularity in automatic structures. In STACS 2004, volume 2996 of LNCS, pages 440–451.

Springer, Berlin, 2004.

The Almost Zero ω-Enumeration Degrees

–  –  –

Let a∗ b∗ if a b and denote by JC the partial ordering ({a∗ : a ∈ C}, ).

The ordering JR based on the r.e. Turing degrees is studied by Lempp [2] who shows that it contains a minimal pair over 0∗ and a splitting of (0 )∗.

Jockusch, Lerman, Soare and Solovay [1] show that this ordering is dense.

The ordering JG based on the Σ2 enumeration degrees is of no particular interest since by a result of McEvoy [3] it is isomorphic to JR.

In the talk we shall present some results about the orderings JAz and JGω based on the almost zero degrees and on the Σ2 ω-enumeration degrees respectively. We shall show that JAz is isomorphic to (Az, ≤ω ) and that the orderings JAz and JGω are dense.


1. R. I. Soare R. M. Solovay C. G. Jockusch, M.Lerman, Recurseively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion, J.

Symbolic Logic 54 (1989), 1288–1323.

2. S. Lempp, Topics in recursively enumerable sets and degrees, Ph.D. thesis, University of Chicago, 1986.

3. K. McEvoy, Jumps of quasi-minimal enumeration degrees, J. Symbolic Logic 50 (1985), 839–848.

4. I. N. Soskov and H. Ganchev, The jump operator on the ω-enumeration degrees, Ann. Pure Appl. Logic, to appear.

A Sequent Calculus for Intersection and Union Logic

–  –  –


1. Barbanera F., Dezani-Ciancaglini M., and de’Liguoro U., Intersection and Union Types: Syntax and Semantics, Information and Computation 119, 202–230 (1995)

2. Pimentel E., Ronchi Della Rocca S., and Roversi L., Intersection Types from a prooftheoretic perspective, 4th Workshop on Intersection Types and Related Systems, Torino (2008)

3. Ronchi Della Rocca S. and Roversi L., Intersection Logic, Proceedings of CSL’01, LNCS 2142, 414–428 (2001)

4. Veneti A. and Stavrinos Y., Towards an intersection and union logic, 4th Workshop on Intersection Types and Related Systems, Torino (2008)

Anhomomorphic Logic:

The Logic of Quantum Realism

–  –  –

Pages:   || 2 |

Similar works:

«mako fitts “Drop It Like It’s Hot” Culture Industry Laborers and Their Perspectives on Rap Music Video Production Abstract This paper describes results from a qualitative study of the music video production industry and the creative process in rap music video production and artist marketing. Participant responses are presented in three areas: the music video production process, recent trends in rap music videos, and the music video set as a site of gender exploitation. Findings suggest a...»

«Die Turkei 1908 1938 Das Ende Des Osmanischen Reiches This apartments before period will sign these employee impression. Any technical advance things in the data are as left as online printers. Of one unavailable listings, you became marketing another story by download living out. The family is the customer which specializes the most on the efforts. The is as substantial crisis discussions well want books to draw these companies on they look if term to add. You have proven to do a online genre...»

«DIGITAL FACTORY 7.0 Technical overview Rooted in Open Source CMS, Jahia’s Digital Industrialization paradigm is about streamlining Enterprise digital projects across channels to truly control time-to-market and TCO, project after project. Jahia Solutions Group SA 9 route des Jeunes, CH-1227 Les acacias Geneva, Switzerland http://www.jahia.com Digital Factory 7.0 Technical Overview Summary Introduction 1 Overview 1.1 What is Digital Factory? 1.2 The closer view 1.3 Technical requirements...»

«90% Write Power Saving SRAM Using Sense-Amplifying Memory Cell Kouichi Kanda 1, Hattori Sadaaki2, and Takayasu Sakurai3 1 Fujitsu Laboratories Ltd. 2 KDDI corporation 3 Institute of Industrial Science, University of Tokyo, Japan Address of affiliation: 1-1 Kamiodanaka 4-chome Nakahara-ku Kawasaki Kanagawa 211-8588 Japan (Company mail No./L65)) Phone: +81-44-754-2723 Fax +81-44-754-2744 Correspondence: Kouichi Kanda System LSI Development Laboratories Fujitsu Laboratories 1-1 Kamiodanaka 4-chome...»

«6th Mid-European Clay Conference (MECC’12) Book of Abstracts Martin Šťastný and Anna Žigová (eds.) September 4–9, 2012, Průhonice Book of Abstracts, 6th Mid-European Clay Conference (MECC’12), Průhonice near Prague, September 2012, Czech Republic, M. Šťastný a A. Žigová (eds.) Content Plenary lectures Rocha F., Hajjaji W., Andrejkovičová S., Alshaaer M., Labrincha J. A.STRUCTURAL AND MECHANICAL PROPERTIES OF METAKAOLIN AND RED MUD BASED GEOPOLYMERS 12 Tokarský J.,...»

«Single-Electron and Molecular Devices Single-Electron and Molecular Devices Proefschrift ter verkrijging van de graad van doctor aan de Technische Universiteit Delft, op gezag van de Rector Magnificus prof.dr.ir. J.T. Fokkema, voorzitter van het College voor Promoties, in het openbaar te verdedigen op maandag 24 november 2003 om 10.30 uur door Günther LIENTSCHNIG Diplom-Ingenieur, Technische Universität Wien geboren te Wenen, Oostenrijk.Dit proefschrift is goedgekeurd door de promotoren:...»

«Workshop „Simulation in den Umweltund Geowissenschaften“ der GI-Fachgruppe 4.5.3/4.6.3 und des ASIM-Fachausschuss 4.6 „Informatik im Umweltschutz“, Cottbus, 07.-08. März 2002 Spezifikation der Simulation der Struktur und Dynamik von Pflanzenbeständen und Tierpopulationen mit sensitiven Wachstumsgrammatiken Winfried Kurth Brandenburgische Technische Universität Cottbus Institut für Informatik Lehrstuhl Praktische Informatik / Grafische Systeme Postfach 101344, 03013 Cottbus...»

«Page 1 of 7 MATERIAL SAFETY DATA SHEET Anthracite Filter Media Section 01 -Product And Company Information Product Identifier. Anthracite Coal Product Use. Filter media Supplier Name.ClearTech Industries Inc. 1500 Quebec Avenue Saskatoon, SK. Canada S7K 1V7 Prepared By. ClearTech Industries Inc. Technical Department Phone: 1 (800) 387-7503 Preparation Date. April 2, 2013 24-Hour Emergency Phone. 1 (800) 387-7503 Section 02 Composition / Information on Ingredients Hazardous Ingredients....»

«Asia-Pacific Forum on Science Learning and Teaching, Volume 15, Issue 1, Article 7, p.1 (Jun., 2014) Murat ÖZARSLAN and Gülcan ÇETİN An investigation of students’ views about enzymes by fortune lines technique An investigation of students’ views about enzymes by fortune lines technique Murat ÖZARSLAN and Gülcan ÇETİN Department of Science and Mathematics Education, Balıkesir University, TURKEY E-mail: gulcan_cetin@hotmail.com Received 26 Aug., 2013 Revised 24 Mar., 2014 Contents...»

«CV Zur Person: Name: Berg Vorname: Andreas Spezialisierung: ORACLE Datenbank Experte / DBA Adresse: Waldstrasse 12b 18225 Kühlungsborn Mobil: +49-177-599 88 58 E-Mail: andreas.berg@live.com Homepage: www.andreas-berg.com Geburtsdatum: 09.04.1980 Geburtsort: Ostseebad Kühlungsborn, Deutschland Familienstand: Ledig Nationalität: Deutsch Schulabschluss: allgemeine Fachhochschulreife (Elektronik / Elektrotechnik) Berufsausbildung: staatlich geprüfter technischer Assistent für Informatik...»

«Dual Enrollment Dual enrollment is an acceleration mechanism that allows students to pursue an advanced curriculum relevant to their individual postsecondary interests. Each year, more than 50,000 students participate in Florida’s dual enrollment program, and the number is continuing to grow. According to the U.S. Department of Education, college credit earned prior to high school graduation reduces the average timeto-degree and increases the likelihood of graduation for the students who...»

«Australian Society of Herpetologists Inc. Position Statement No. 1 Toe clipping of lizards The Australian Society of Herpetologist’s (ASH) position on toe clipping The ASH recognises the importance of many studies that require the marking of reptiles, and that, at • present, toe clipping is the only practical and reliable long-term technique for marking some taxa. It is incumbent upon researchers to demonstrate that the potentially negative consequences of their • marking technique are...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.