Theory and applications of models of computation : 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007 : proceedings
著者
書誌事項
Theory and applications of models of computation : 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007 : proceedings
(Lecture notes in computer science, 4484)
Springer, c2007
大学図書館所蔵 全5件
  青森
  岩手
  宮城
  秋田
  山形
  福島
  茨城
  栃木
  群馬
  埼玉
  千葉
  東京
  神奈川
  新潟
  富山
  石川
  福井
  山梨
  長野
  岐阜
  静岡
  愛知
  三重
  滋賀
  京都
  大阪
  兵庫
  奈良
  和歌山
  鳥取
  島根
  岡山
  広島
  山口
  徳島
  香川
  愛媛
  高知
  福岡
  佐賀
  長崎
  熊本
  大分
  宮崎
  鹿児島
  沖縄
  韓国
  中国
  タイ
  イギリス
  ドイツ
  スイス
  フランス
  ベルギー
  オランダ
  スウェーデン
  ノルウェー
  アメリカ
注記
Includes bibliographical references and index
内容説明・目次
内容説明
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. It addresses all major areas in computer science; mathematics, especially logic; and the physical sciences, particularly with regard to computation and computability theory. The papers particularly focus on algorithms, complexity and computability theory.
目次
Plenary Lectures.- Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm.- Generalizations of the Compactness Theorem and Goedel's Completeness Theorem for Nonstandard Finite Structures.- Contributed Papers.- Approximation Algorithms for 3D Orthogonal Knapsack.- A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences.- The Hardness of Selective Network Design for Bottleneck Routing Games.- A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns.- Elementary Differences Among Jump Hierarchies.- Working with the LR Degrees.- Computability on Subsets of Locally Compact Spaces.- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs.- Finding a Duplicate and a Missing Item in a Stream.- Directed Searching Digraphs: Monotonicity and Complexity.- Protecting Against Key Escrow and Key Exposure in Identity-Based Cryptosystem.- Encapsulated Scalar Multiplications and Line Functions in the Computation of Tate Pairing.- A Provably Secure Blind Signature Scheme.- Construct Public Key Encryption Scheme Using Ergodic Matrices over GF(2).- New Left-to-Right Radix-r Signed-Digit Recoding Algorithm for Pairing-Based Cryptosystems.- The Strongest Nonsplitting Theorem.- There is an Sw-Cuppable Strongly c.e. Real.- On Computation Complexity of the Concurrently Enabled Transition Set Problem.- Synchronization of Some DFA.- On the Treewidth and Pathwidth of Biconvex Bipartite Graphs.- On Exact Complexity of Subgraph Homeomorphism.- Searching a Polygonal Region by Two Guards.- On the Internal Steiner Tree Problem.- Approximately Optimal Trees for Group Key Management with Batch Updates.- On Deciding Deep Holes of Reed-Solomon Codes.- Quantum Multiparty Communication Complexity and Circuit Lower Bounds.- Efficient Computation of Algebraic Immunity of Symmetric Boolean Functions.- Improving the Average Delay of Sorting.- Approximating Capacitated Tree-Routings in Networks.- Feedback Arc Set Problem in Bipartite Tournaments.- Studying on Economic-Inspired Mechanisms for Routing and Forwarding in Wireless Ad Hoc Network.- Enhancing Simulation for Checking Language Containment.- QBF-Based Symbolic Model Checking for Knowledge and Time.- A Characterization of the Language Classes Learnable with Correction Queries.- Learnable Algorithm on the Continuum.- Online Deadline Scheduling with Bounded Energy Efficiency.- Efficient Algorithms for Airline Problem.- Efficient Exact Arithmetic over Constructive Reals.- Bounding Run-Times of Local Adiabatic Algorithms.- A Note on Universal Composable Zero Knowledge in Common Reference String Model.- A Note on the Feasibility of Generalized Universal Composability.- t-Private and Secure Auctions.- Secure Multiparty Computations Using a Dial Lock.- A Time Hierarchy Theorem for Nondeterministic Cellular Automata.- Decidability of Propositional Projection Temporal Logic with Infinite Models.- Separation of Data Via Concurrently Determined Discriminant Functions.- The Undecidability of the Generalized Collatz Problem.- Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces.- Maximum Edge-Disjoint Paths Problem in Planar Graphs.- An Efficient Algorithm for Generating Colored Outerplanar Graphs.- Orthogonal Drawings for Plane Graphs with Specified Face Areas.- Absolutely Non-effective Predicates and Functions in Computable Analysis.- Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary Sequences.- The Existence of Unsatisfiable Formulas in k-LCNF for k???3.- Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model.- Phase Transition of Multivariate Polynomial Systems.- Approximation Algorithms for Maximum Edge Coloring Problem.- Two Improved Range-Efficient Algorithms for F 0 Estimation.- Approximation to the Minimum Rooted Star Cover Problem.- Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems.- Parameterized Algorithms for Weighted Matching and Packing Problems.- Kernelizations for Parameterized Counting Problems.- Revisiting the Impossibility for Boosting Service Resilience.- An Approximation Algorithm to the k-Steiner Forest Problem.- A Distributed Algorithm of Fault Recovery for Stateful Failover.- Path Embedding on Folded Hypercubes.- An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs.
「Nielsen BookData」 より