Theory and Applications of Models of Computation: 4th International Conference, Tamc 2007, Shanghai, China, May 22-25, 2007, Proceedings

by Cai, Jin-Yi; Cooper, S. Barry; Zhu, Hong; Rojo, Jaime

• ISBN13: 9783540725039
• ISBN10: 3540725032
• Format: Paperback
• Copyright: 2007-06-12
• Publisher: Springer Verlag

Summary

This book constitutes the refereed proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. The 67 revised full papers presented together with 2 plenary lectures were carefully reviewed and selected from over 500 submissions. All major areas in computer science, mathematics (especially logic) and the physical sciences particularly with regard to computation and computability theory are addressed. The papers - featuring this crossdisciplinary character - particularly focus on algorithms, complexity and computability theory, giving the conference a special flavor and distinction.

Table of Contents

Detecting sharp drops in PageRank and a simplified local partitioning algorithm	p. 1
Generalizations of the compactness theorem and Godel's completeness theorem for nonstandard finite structures	p. 13
Approximation algorithms for 3D orthogonal knapsack	p. 34
A comparative study of efficient algorithms for partitioning a sequence into monotone subsequence	p. 46
The hardness of selective network design for bottleneck routing games	p. 58
A polynomial time algorithm for finding linear interval graph patterns	p. 67
Elementary differences among jump hierarchies	p. 79
Working with the LR degrees	p. 89
Computability on subsets of locally compact spaces	p. 100
A new approach to graph recognition and applications to distance-hereditary graphs	p. 115
Finding a duplicate and a missing item in a stream	p. 128
Directed searching digraphs : monotonicity and complexity	p. 136
Protecting against key escrow and key exposure in identity-based cryptosystem	p. 148
Encapsulated scalar multiplications and line functions in the computation of Tate pairing	p. 159
A provably secure blind signature scheme	p. 171
Construct public key encryption scheme using ergodic matrices over GF(2)	p. 181
New left-to-right radix-r signed-digit recoding algorithm for pairing-based cryptosystems	p. 189
The strongest nonsplitting theorem	p. 199
There is an Sw-cuppable strongly c.e. real	p. 212
On computation complexity of the concurrently enabled transition set problem	p. 222
Synchronization of some DFA	p. 234
On the treewidth and pathwidth of biconvex bipartite graphs	p. 244
On exact complexity of subgraph homeomorphism	p. 256
Searching a polygonal region by two guards	p. 262
On the internal Steiner tree problem	p. 274
Approximately optimal trees for group key management with batch updates	p. 284
On deciding deep holes of Reed-Solomon codes	p. 296
Quantum multiparty communication complexity and circuit lower bounds	p. 306
Efficient computation of algebraic immunity of symmetric boolean functions	p. 318
Improving the average delay of sorting	p. 330
Approximating capacitated tree-routings in networks	p. 342
Feedback arc set problem in bipartite tournaments	p. 354
Studying on economic-inspired mechanisms for routing and forwarding in wireless ad hoc network	p. 362
Enhancing simulation for checking language containment	p. 374
QBF-based symbolic model checking for knowledge and time	p. 386
A characterization of the language classes learnable with correction queries	p. 398
Learnable algorithm on the continuum	p. 408
Online deadline scheduling with bounded energy efficiency	p. 416
Efficient algorithms for airline problem	p. 428
Efficient exact arithmetic over constructive reals	p. 440
Bounding run-times of local adiabatic algorithms	p. 450
A note on universal composable zero knowledge in common reference string model	p. 462
A note on the feasibility of generalized universal cornposability	p. 474
t-Private and secure auctions	p. 486
Secure multiparty computations using a dial lock	p. 499
A time hierarchy theorem for nondeterministic cellular automata	p. 511
Decidability of propositional projection temporal logic with infinite models	p. 521
Separation of data via concurrently determined discriminant functions	p. 533
The undecidability of the generalized collatz problem	p. 542
Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-euclidean spaces	p. 554
Maximum edge-disjoint paths problem in planar graphs	p. 566
An efficient algorithm for generating colored outerplanar graphs	p. 573
Orthogonal drawings for plane graphs with specified face areas	p. 584
Absolutely non-effective predicates and functions in computable analysis	p. 595
Linear-size log-depth negation-limited inverter for k-tonic binary sequences	p. 605
The existence of unsatisfiable formulas in k-LCNF for k [actual symbol not reproducible] 3	p. 616
Improved exponential time lower bound of knapsack problem under BT model	p. 624
Phase transition of multivariate polynomial systems	p. 632
Approximation algorithms for maximum edge coloring problem	p. 646
Two improved range-efficient algorithms for f[subscript o] estimation	p. 659
Approximation to the minimum rooted star cover problem	p. 670
Approximability and parameterized complexity of consecutive ones submatrix problems	p. 680
Parameterized algorithms for weighted matching and packing problems	p. 692
Keruelizations for parameterized counting problems	p. 703
Revisiting the impossibility for boosting service resilience	p. 715
An approximation algorithm to the k-Steiner forest problem	p. 728
A distributed algorithm of fault recovery for stateful failover	p. 738
Path embedding on folded hypercubes	p. 750
An approximation algorithm based on chain implication for constrained minimum vertex covers in bipartite graphs	p. 760
Table of Contents provided by Blackwell. All Rights Reserved.