Skip to main content
SpringerLink
Log in
Book cover

Theory and Applications of Models of Computation

5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008, Proceedings

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Manindra Agrawal
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Dingzhu Du
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Zhenhua Duan
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Angsheng Li
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 4978)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: TAMC 2008.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (51 papers)

  1. Front Matter

    Download chapter PDF

  2. Plenary Lectures

    1. Differential Privacy: A Survey of Results

      • Cynthia Dwork
      Pages 1-19

  3. Special Session Lectures

    1. On the Complexity of Measurement in Classical Physics

      • Edwin Beggs, José Félix Costa, Bruno Loff, John Tucker
      Pages 20-30

    2. Quantum Walk Based Search Algorithms

      • Miklos Santha
      Pages 31-46

  4. Contributed Lectures

    1. Propositional Projection Temporal Logic, B\(\ddot{u}\)chi Automata and ω-Regular Expressions

      • Cong Tian, Zhenhua Duan
      Pages 47-58

    2. Genome Rearrangement Algorithms for Unsigned Permutations with O(logn) Singletons

      • Xiaowen Lou, Daming Zhu
      Pages 59-69

    3. On the Complexity of the Hidden Subgroup Problem

      • Stephen Fenner, Yong Zhang
      Pages 70-81

    4. An O *(3.523k) Parameterized Algorithm for 3-Set Packing

      • Jianxin Wang, Qilong Feng
      Pages 82-93

    5. Indistinguishability and First-Order Logic

      • Skip Jordan, Thomas Zeugmann
      Pages 94-104

    6. Derandomizing Graph Tests for Homomorphism

      • Angsheng Li, Linqing Tang
      Pages 105-115

    7. Definable Filters in the Structure of Bounded Turing Reductions

      • Angsheng Li, Weilin Li, Yicheng Pan, Linqing Tang
      Pages 116-124

    8. Distance Constrained Labelings of Trees

      • Jiří Fiala, Petr A. Golovach, Jan Kratochvíl
      Pages 125-135

    9. A Characterization of NC k by First Order Functional Programs

      • Jean-Yves Marion, Romain Péchoux
      Pages 136-147

    10. The Structure of Detour Degrees

      • Lars Kristiansen, Paul J. Voda
      Pages 148-159

    11. Hamiltonicity of Matching Composition Networks with Conditional Edge Faults

      • Sun-Yuan Hsieh, Chia-Wei Lee
      Pages 160-169

    12. Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs

      • J. Czyzowicz, S. Dobrev, H. González-Aguilar, R. Kralovic, E. Kranakis, J. Opatrny et al.
      Pages 170-181

    13. Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity

      • Petr Golovach, Jan Kratochvíl
      Pages 182-191

    14. More on Weak Bisimilarity of Normed Basic Parallel Processes

      • Haiyan Chen
      Pages 192-203

    15. Extensions of Embeddings in the Computably Enumerable Degrees

      • Jitai Zhao
      Pages 204-211

    16. An Improved Parameterized Algorithm for a Generalized Matching Problem

      • Jianxin Wang, Dan Ning, Qilong Feng, Jianer Chen
      Pages 212-222
Back to top

Other volumes

  1. Theory and Applications of Models of Computation

Keywords

About this book

This book constitutes the refereed proceedings of the 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008, held in Xi'an, China in April 2008.

The 48 revised full papers presented together with 2 invited talks and 1 plenary lecture were carefully reviewed and selected from 192 submissions. The papers address current issues of all major areas in computer science, mathematics (especially logic) and the physical sciences - computation, algorithms, complexity and computability theory in particular. With this crossdisciplinary character the conference is given a special flavor and distinction.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation