Theory and Applications of Models of Computation: Third International Conference, TAMC 2006, Beijing, China, May 15-20, 2006. Proceedings

Front Matter....Pages -
On-Line Algorithms, Real Time, the Virtue of Laziness, and the Power of Clairvoyance....Pages 1-20
Similarity of Objects and the Meaning of Words....Pages 21-45
Totally < ω ω Computably Enumerable and m -topped Degrees....Pages 46-60
Mitosis in Computational Complexity....Pages 61-67
Models of Intuitionistic Set Theories over Partial Combinatory Algebras....Pages 68-78
Width Versus Size in Resolution Proofs....Pages 79-88
Recent Progress in Quantum Computational Complexity....Pages 89-89
On Several Scheduling Problems with Rejection or Discretely Compressible Processing Times....Pages 90-98
LS-SVM Based on Chaotic Particle Swarm Optimization with Simulated Annealing....Pages 99-107
A Bounded Item Bin Packing Problem over Discrete Distribution....Pages 108-117
Scheduling Jobs on a Flexible Batching Machine: Model, Complexity and Algorithms....Pages 118-127
Faster Algorithms for Sorting by Transpositions and Sorting by Block-Interchanges....Pages 128-137
An ACO-Based Approach for Task Assignment and Scheduling of Multiprocessor Control Systems....Pages 138-147
Adversary Immune Size Approximation of Single-Hop Radio Networks....Pages 148-158
On Load-Balanced Semi-matchings for Weighted Bipartite Graphs....Pages 159-170
Analyzing Chain Programs over Difference Constraints....Pages 171-180
Linear-Time 2-Approximation Algorithm for the Watchman Route Problem....Pages 181-191
Further Properties of Cayley Digraphs and Their Applications to Interconnection Networks....Pages 192-197
Real Time Critical Edge of the Shortest Path in Transportation Networks....Pages 198-205
Finding Min-Sum Disjoint Shortest Paths from a Single Source to All Pairs of Destinations....Pages 206-216
A New Approximation Algorithm for the k -Facility Location Problem....Pages 217-230
Alternative Measures of Computational Complexity with Applications to Agnostic Learning....Pages 231-235
Disjoint NP -Pairs from Propositional Proof Systems....Pages 236-247
Valiant’s Holant Theorem and Matchgate Tensors....Pages 248-261
Variable Minimal Unsatisfiability....Pages 262-273
A New Lower Bound of Critical Function for (k,s)-SAT....Pages 274-282
Cluster Computing and the Power of Edge Recognition....Pages 283-294
Quadratic Lower Bounds on Matrix Rigidity....Pages 295-307
Non-reducible Descriptions for Conditional Kolmogorov Complexity....Pages 308-317
Generalized Counters and Reversal Complexity....Pages 318-326
Multisource Algorithmic Information Theory....Pages 327-338
Block Sensitivity of Weakly Symmetric Functions....Pages 339-344
Optimization Problems in the Polynomial-Time Hierarchy....Pages 345-355
#3-Regular Bipartite Planar Vertex Cover is #P-Complete....Pages 356-364
Group Theory Based Synthesis of Binary Reversible Circuits....Pages 365-374
On Some Complexity Issues of NC Analytic Functions....Pages 375-386
Learning Juntas in the Presence of Noise....Pages 387-398
Grey Reinforcement Learning for Incomplete Information Processing....Pages 399-407
On the Foundations of Universal Sequence Prediction....Pages 408-420
Some Recent Results in U-Shaped Learning....Pages 421-431
Learning Overcomplete Representations with a Generalized Gaussian Prior....Pages 432-441
On PAC Learning Algorithms for Rich Boolean Function Classes....Pages 442-451
On-Line Regression Competitive with Reproducing Kernel Hilbert Spaces....Pages 452-463
Inductive Inference and Language Learning....Pages 464-473
Time Series Predictions Using Multi-scale Support Vector Regressions....Pages 474-481
Identification and Comparison of Motifs in Brain-Specific and Muscle-Specific Alternative Splicing....Pages 482-493
On Probe Permutation Graphs....Pages 494-504
Automatic Classification of Protein Structures Based on Convex Hull Representation by Integrated Neural Network....Pages 505-514
Protein Structure Comparison Based on a Measure of Information Discrepancy....Pages 515-527
Succinct Text Indexes on Large Alphabet....Pages 528-537
Identity-Based Threshold Proxy Signature Scheme with Known Signers....Pages 538-546
Secure Computations in a Minimal Model Using Multiple-Valued ESOP Expressions....Pages 547-554
Towards Practical Computable Functions on Context-Free Languages....Pages 555-565
The Extended Probabilistic Powerdomain Monad over Stably Compact Spaces....Pages 566-575
Analysis of Properties of Petri Synthesis Net....Pages 576-587
A Tree Construction of the Preferable Answer Sets for Prioritized Basic Disjunctive Logic Programs....Pages 588-600
Object-Oriented Specification Composition and Refinement Via Category Theoretic Computations....Pages 601-610
Improved SAT Based Bounded Model Checking....Pages 611-620
Encodings and Arithmetic Operations in Membrane Computing....Pages 621-630
The General Purpose Analog Computer and Computable Analysis are Two Equivalent Paradigms of Analog Computation....Pages 631-643
Forecasting Black Holes in Abstract Geometrical Computation is Highly Unpredictable....Pages 644-653
The Trade-Off Theorem and Fragments of Gödel’s T ....Pages 654-674
On Non-binary Quantum BCH Codes....Pages 675-683
Maximal Models of Assertion Graph in GSTE....Pages 684-693
Immunity Properties and the n -C.E. Hierarchy....Pages 694-703
On Rogers Semilattices....Pages 704-706
Invertible Classes....Pages 707-720
Universal Cupping Degrees....Pages 721-730
On the Quotient Structure of Computably Enumerable Degrees Modulo the Noncuppable Ideal....Pages 731-736
Enumeration Degrees of the Bounded Total Sets....Pages 737-745
A Generic Set That Does Not Bound a Minimal Pair....Pages 746-755
Lowness for Weakly 1-generic and Kurtz-Random....Pages 756-764
On Differences Among Elementary Theories of Finite Levels of Ershov Hierarchies....Pages 765-771
On Mass Problems of Presentability....Pages 772-782
Beyond the First Main Theorem – When Is the Solution of a Linear Cauchy Problem Computable?....Pages 783-792
Back Matter....Pages -