Fundamentals of Computation Theory
Liśkiewicz, Maciej.
Fundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005. Proceedings / [electronic resource] : edited by Maciej Liśkiewicz, Rüdiger Reischuk. - XV, 576 p. Also available online. online resource. - Lecture Notes in Computer Science, 3623 0302-9743 ; . - Lecture Notes in Computer Science, 3623 .
Invited Talks -- The Complexity of Querying External Memory and Streaming Data -- The Smoothed Analysis of Algorithms -- Path Coupling Using Stopping Times -- Circuits -- On the Incompressibility of Monotone DNFs -- Bounds on the Power of Constant-Depth Quantum Circuits -- Automata I -- Biautomatic Semigroups -- Deterministic Automata on Unranked Trees -- Complexity I -- Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals -- Generic Density and Small Span Theorem -- Approximability -- Logspace Optimization Problems and Their Approximability Properties -- A Faster and Simpler 2-Approximation Algorithm for Block Sorting -- Computational and Structural Complexity -- On the Power of Unambiguity in Alternating Machines -- Translational Lemmas for Alternating TMs and PRAMs -- Collapsing Recursive Oracles for Relativized Polynomial Hierarchies -- Graphs and Complexity -- Exact Algorithms for Graph Homomorphisms -- Improved Algorithms and Complexity Results for Power Domination in Graphs -- Clique-Width for Four-Vertex Forbidden Subgraphs -- Computational Game Theory -- On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems -- Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems -- Visual Cryptography and Computational Geometry -- Perfect Reconstruction of Black Pixels Revisited -- Adaptive Zooming in Point Set Labeling -- Query Complexity -- On the Black-Box Complexity of Sperner’s Lemma -- Property Testing and the Branching Program Size of Boolean Functions -- Distributed Systems -- Almost Optimal Explicit Selectors -- The Delayed k-Server Problem -- Automata and Formal Languages -- Leftist Grammars and the Chomsky Hierarchy -- Shrinking Multi-pushdown Automata -- Graph Algorithms -- A Simple and Fast Min-cut Algorithm -- (Non)-Approximability for the Multi-criteria TSP(1,2) -- Semantics -- Completeness and Compactness of Quantitative Domains -- A Self-dependency Constraint in the Simply Typed Lambda Calculus -- A Type System for Computationally Secure Information Flow -- Approximation Algorithms -- Algorithms for Graphs Embeddable with Few Crossings Per Edge -- Approximation Results for the Weighted P 4 Partition Problems -- The Maximum Resource Bin Packing Problem -- Average-Case Complexity -- Average-Case Non-approximability of Optimisation Problems -- Relations Between Average-Case and Worst-Case Complexity -- Algorithms -- Reconstructing Many Partitions Using Spectral Techniques -- Constant Time Generation of Linear Extensions -- Complexity II -- On Approximating Real-World Halting Problems -- An Explicit Solution to Post’s Problem over the Reals -- The Complexity of Semilinear Problems in Succinct Representation -- Graph Algorithms -- On Finding Acyclic Subhypergraphs -- An Improved Approximation Algorithm for TSP with Distances One and Two -- New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem -- Automata II -- On the Expressiveness of Asynchronous Cellular Automata -- Tree Automata and Discrete Distributed Games -- Pattern Matching -- A New Linearizing Restriction in the Pattern Matching Problem -- Fully Incremental LCS Computation.
This volume is dedicated to the 15th Symposium on Fundamentals of Com- tation Theory FCT 2005, held in Lu ¨beck, Germany, on August 17–20, 2005. The FCT symposium was established in 1977 as a biennial event for - searchers interested in all aspects of theoretical computer science, in particular in algorithms, complexity, and formal and logical methods. The previous FCT conferences were held in the following places: Poznan ´ (Poland, 1977),Wendisch- Rietz (Germany, 1979), Szeged (Hungary, 1981), Borgholm (Sweden, 1983), Cottbus(Germany,1985),Kazan(Russia,1987),Szeged(Hungary,1989),Gosen- Berlin (Germany, 1991), Szeged (Hungary, 1993), Dresden (Germany, 1995), Krak´ ow (Poland, 1997), Iasi (Romania, 1999), Riga (Latvia, 2001) and Malmo ¨ (Sweden, 2003). The FCT conference seriesis coordinatedby a steering comm- tee. Its current members are B. Chlebus (Denver/Warsaw),Z. Esik (Szeged), M. Karpinski (Bonn), A. Lingas (Lund), M. Santha (Paris), E. Upfal (Providence) and I. Wegener (Dortmund). The call for papers for FCT 2005 sought contributions on original research in all aspects of theoretical computer science including design and analysis of algorithms, abstract data types, approximation algorithms, automata and formal languages, categorical and topological approaches, circuits, computational and structural complexity, circuit and proof theory, computational biology, com- tational geometry, computer systems theory, concurrency theory, cryptography, domain theory, distributed algorithms and computation, molecular computation, quantumcomputation and information, granular computation, probabilistic c- putation, learning theory, rewriting, semantics, logic in computer science, spe- ?cation, transformation and veri?cation, and algebraic aspects of computer s- ence.
9783540318736
10.1007/11537311 doi
Computer science.
Computer software.
Computational complexity.
Computer graphics.
Computer Science.
Computation by Abstract Devices.
Algorithm Analysis and Problem Complexity.
Mathematical Logic and Formal Languages.
Discrete Mathematics in Computer Science.
Computer Graphics.
QA75.5-76.95
004.0151
Fundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005. Proceedings / [electronic resource] : edited by Maciej Liśkiewicz, Rüdiger Reischuk. - XV, 576 p. Also available online. online resource. - Lecture Notes in Computer Science, 3623 0302-9743 ; . - Lecture Notes in Computer Science, 3623 .
Invited Talks -- The Complexity of Querying External Memory and Streaming Data -- The Smoothed Analysis of Algorithms -- Path Coupling Using Stopping Times -- Circuits -- On the Incompressibility of Monotone DNFs -- Bounds on the Power of Constant-Depth Quantum Circuits -- Automata I -- Biautomatic Semigroups -- Deterministic Automata on Unranked Trees -- Complexity I -- Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals -- Generic Density and Small Span Theorem -- Approximability -- Logspace Optimization Problems and Their Approximability Properties -- A Faster and Simpler 2-Approximation Algorithm for Block Sorting -- Computational and Structural Complexity -- On the Power of Unambiguity in Alternating Machines -- Translational Lemmas for Alternating TMs and PRAMs -- Collapsing Recursive Oracles for Relativized Polynomial Hierarchies -- Graphs and Complexity -- Exact Algorithms for Graph Homomorphisms -- Improved Algorithms and Complexity Results for Power Domination in Graphs -- Clique-Width for Four-Vertex Forbidden Subgraphs -- Computational Game Theory -- On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems -- Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems -- Visual Cryptography and Computational Geometry -- Perfect Reconstruction of Black Pixels Revisited -- Adaptive Zooming in Point Set Labeling -- Query Complexity -- On the Black-Box Complexity of Sperner’s Lemma -- Property Testing and the Branching Program Size of Boolean Functions -- Distributed Systems -- Almost Optimal Explicit Selectors -- The Delayed k-Server Problem -- Automata and Formal Languages -- Leftist Grammars and the Chomsky Hierarchy -- Shrinking Multi-pushdown Automata -- Graph Algorithms -- A Simple and Fast Min-cut Algorithm -- (Non)-Approximability for the Multi-criteria TSP(1,2) -- Semantics -- Completeness and Compactness of Quantitative Domains -- A Self-dependency Constraint in the Simply Typed Lambda Calculus -- A Type System for Computationally Secure Information Flow -- Approximation Algorithms -- Algorithms for Graphs Embeddable with Few Crossings Per Edge -- Approximation Results for the Weighted P 4 Partition Problems -- The Maximum Resource Bin Packing Problem -- Average-Case Complexity -- Average-Case Non-approximability of Optimisation Problems -- Relations Between Average-Case and Worst-Case Complexity -- Algorithms -- Reconstructing Many Partitions Using Spectral Techniques -- Constant Time Generation of Linear Extensions -- Complexity II -- On Approximating Real-World Halting Problems -- An Explicit Solution to Post’s Problem over the Reals -- The Complexity of Semilinear Problems in Succinct Representation -- Graph Algorithms -- On Finding Acyclic Subhypergraphs -- An Improved Approximation Algorithm for TSP with Distances One and Two -- New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem -- Automata II -- On the Expressiveness of Asynchronous Cellular Automata -- Tree Automata and Discrete Distributed Games -- Pattern Matching -- A New Linearizing Restriction in the Pattern Matching Problem -- Fully Incremental LCS Computation.
This volume is dedicated to the 15th Symposium on Fundamentals of Com- tation Theory FCT 2005, held in Lu ¨beck, Germany, on August 17–20, 2005. The FCT symposium was established in 1977 as a biennial event for - searchers interested in all aspects of theoretical computer science, in particular in algorithms, complexity, and formal and logical methods. The previous FCT conferences were held in the following places: Poznan ´ (Poland, 1977),Wendisch- Rietz (Germany, 1979), Szeged (Hungary, 1981), Borgholm (Sweden, 1983), Cottbus(Germany,1985),Kazan(Russia,1987),Szeged(Hungary,1989),Gosen- Berlin (Germany, 1991), Szeged (Hungary, 1993), Dresden (Germany, 1995), Krak´ ow (Poland, 1997), Iasi (Romania, 1999), Riga (Latvia, 2001) and Malmo ¨ (Sweden, 2003). The FCT conference seriesis coordinatedby a steering comm- tee. Its current members are B. Chlebus (Denver/Warsaw),Z. Esik (Szeged), M. Karpinski (Bonn), A. Lingas (Lund), M. Santha (Paris), E. Upfal (Providence) and I. Wegener (Dortmund). The call for papers for FCT 2005 sought contributions on original research in all aspects of theoretical computer science including design and analysis of algorithms, abstract data types, approximation algorithms, automata and formal languages, categorical and topological approaches, circuits, computational and structural complexity, circuit and proof theory, computational biology, com- tational geometry, computer systems theory, concurrency theory, cryptography, domain theory, distributed algorithms and computation, molecular computation, quantumcomputation and information, granular computation, probabilistic c- putation, learning theory, rewriting, semantics, logic in computer science, spe- ?cation, transformation and veri?cation, and algebraic aspects of computer s- ence.
9783540318736
10.1007/11537311 doi
Computer science.
Computer software.
Computational complexity.
Computer graphics.
Computer Science.
Computation by Abstract Devices.
Algorithm Analysis and Problem Complexity.
Mathematical Logic and Formal Languages.
Discrete Mathematics in Computer Science.
Computer Graphics.
QA75.5-76.95
004.0151