Amazon cover image
Image from Amazon.com

Mathematical Foundations of Computer Science 2004 : 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings / edited by Jiří Fiala, Václav Koubek, Jan Kratochvíl.

By: Fiala, JiříContributor(s): Koubek, Václav | Kratochvíl, JanMaterial type: TextTextSeries: Serienbezeichnung | Lecture notes in computer science ; 3153.Publication details: Berlin, Heidelberg : Springer Berlin Heidelberg, 2004. Description: 1 online resource (XIV, 902 pages Also available online.)Content type: text Media type: computer Carrier type: online resourceISBN: 9783540286295; 3540286292Subject(s): Computer science | Data structures (Computer science) | Computer software | Logic design | Computational complexity | Algorithms | Informatique -- Mathématiques -- Congrès | COMPUTERS -- Hardware -- Mainframes & Minicomputers | Algorithms | Computational complexity | Computer science | Computer software | Data structures (Computer science) | Logic designGenre/Form: Electronic books. Additional physical formats: Print version:: No titleDDC classification: 005.1 LOC classification: QA76.9.A43Online resources: Click here to access online
Contents:
Invited Lectures -- A Case Study of Genome Evolution: From Continuous to Discrete Time Model -- Multicoloring: Problems and Techniques -- Some Recent Progress in Algorithmic Randomness -- Ubiquitous Parameterization -- Invitation to Fixed-Parameter Algorithms -- PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness -- Theory and Applied Computing: Observations and Anecdotes -- Boxed Ambients with Communication Interfaces -- Algebraic Recognizability of Languages -- Geometric Optimization and Unique Sink Orientations of Cubes -- Congestion Games and Coordination Mechanisms -- Graph Algorithms -- Equitable Colorings of Bounded Treewidth Graphs -- The Bidimensional Theory of Bounded-Genus Graphs -- Parallel Knock-Out Schemes in Networks -- Online Algorithms for Disk Graphs -- Approximations -- Protein Folding in the HP Model on Grid Lattices with Diagonals -- Optimization, Games, and Quantified Constraint Satisfaction -- Approximating Boolean Functions by OBDDs -- On Approximation Hardness of the Minimum 2SAT-DELETION Problem -- Graphs and Complexity -- Group Coloring and List Group Coloring Are?2 P -Complete -- Complexity Results in Graph Reconstruction -- Generating Paths and Cuts in Multi-pole (Di)graphs -- Packing Directed Cycles Efficiently -- Circuits -- The Complexity of Membership Problems for Circuits over Sets of Integers -- Some Meet-in-the-Middle Circuit Lower Bounds -- The Enumerability of P Collapses P to NC -- On NC1 Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge -- General Complexity -- All Superlinear Inverse Schemes Are coNP-Hard -- The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups -- Generation Problems -- One Query Reducibilities Between Partial Information Classes -- Automata -- A New Dimension Sensitive Property for Cellular Automata -- Captive Cellular Automata -- Simulating 3D Cellular Automata with 2D Cellular Automata -- Graph Exploration by a Finite Automaton -- Parametrized and Kolmogorov Complexity -- On Polynomially Time Bounded Symmetry of Information -- Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets -- A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs -- Polynomial Time Approximation Schemes and Parameterized Complexity -- Semantics -- Epistemic Foundation of the Well-Founded Semantics over Bilattices -- Structural Model Checking for Communicating Hierarchical Machines -- Compositional Verification: Decidability Issues Using Graph Substitutions -- Event Structures for Resolvable Conflict -- Scheduling -- Optimal Preemptive Scheduling for General Target Functions -- The Price of Anarchy for Polynomial Social Cost -- Agent-Based Information Handling in Large Networks -- Approximating Earliest Arrival Flows with Flow-Dependent Transit Times -- Algebraic Theory of Languages -- A Hierarchy of Irreducible Sofic Shifts -- Membership and Reachability Problems for Row-Monomial Transformations -- On Pseudovarieties of Semiring Homomorphisms -- An Algebraic Generalization of?-Regular Languages -- Games -- A Protocol for Serializing Unique Strategies -- A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games -- When Can You Play Positionally? -- Languages -- The Dual of Concatenation -- Computational Aspects of Disjunctive Sequences -- Decidability of Trajectory-Based Equations -- Geometry -- Efficient View Point Selection for Silhouettes of Convex Polyhedra -- Angles and Lengths in Reconfigurations of Polygons and Polyhedra -- Improved Bounds and Schemes for the Declustering Problem -- Crossing Number Is Hard for Cubic Graphs -- Languages and Complexity -- A Reducibility for the Dot-Depth Hierarchy -- Sublogarithmic Ambiguity -- An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx -- A Generalization of Repetition Threshold -- Quantum Computing -- An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation -- Universal Test for Quantum One-Way Permutations -- A Common Algebraic Description for Probabilistic and Quantum Computations -- XML -- Extraction and Implication of Path Constraints -- Schema Evolution for XML: A Consistency-Preserving Approach -- Complexity of Decision Problems for Simple Regular Expressions.
Summary: This book constitutes the refereed proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science, MFCS 2004, held in Prague, Czech Republic in August 2004. The 60 revised full papers presented together with full papers or abstracts of 10 invited talks were carefully reviewed and selected from 167 submissions. The papers are organised in topical sections on graph algorithms, approximation, graphs and complexity, circuits, general complexity, automata, parameterized and kolmogrov complexity, semantics, scheduling, algebraic theory of languages, games, languages, geometry, languages and complexity, quantum computing, and XML.
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library

Electronic Book@IST

EBook Available
Total holds: 0

This book constitutes the refereed proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science, MFCS 2004, held in Prague, Czech Republic in August 2004. The 60 revised full papers presented together with full papers or abstracts of 10 invited talks were carefully reviewed and selected from 167 submissions. The papers are organised in topical sections on graph algorithms, approximation, graphs and complexity, circuits, general complexity, automata, parameterized and kolmogrov complexity, semantics, scheduling, algebraic theory of languages, games, languages, geometry, languages and complexity, quantum computing, and XML.

Invited Lectures -- A Case Study of Genome Evolution: From Continuous to Discrete Time Model -- Multicoloring: Problems and Techniques -- Some Recent Progress in Algorithmic Randomness -- Ubiquitous Parameterization -- Invitation to Fixed-Parameter Algorithms -- PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness -- Theory and Applied Computing: Observations and Anecdotes -- Boxed Ambients with Communication Interfaces -- Algebraic Recognizability of Languages -- Geometric Optimization and Unique Sink Orientations of Cubes -- Congestion Games and Coordination Mechanisms -- Graph Algorithms -- Equitable Colorings of Bounded Treewidth Graphs -- The Bidimensional Theory of Bounded-Genus Graphs -- Parallel Knock-Out Schemes in Networks -- Online Algorithms for Disk Graphs -- Approximations -- Protein Folding in the HP Model on Grid Lattices with Diagonals -- Optimization, Games, and Quantified Constraint Satisfaction -- Approximating Boolean Functions by OBDDs -- On Approximation Hardness of the Minimum 2SAT-DELETION Problem -- Graphs and Complexity -- Group Coloring and List Group Coloring Are?2 P -Complete -- Complexity Results in Graph Reconstruction -- Generating Paths and Cuts in Multi-pole (Di)graphs -- Packing Directed Cycles Efficiently -- Circuits -- The Complexity of Membership Problems for Circuits over Sets of Integers -- Some Meet-in-the-Middle Circuit Lower Bounds -- The Enumerability of P Collapses P to NC -- On NC1 Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge -- General Complexity -- All Superlinear Inverse Schemes Are coNP-Hard -- The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups -- Generation Problems -- One Query Reducibilities Between Partial Information Classes -- Automata -- A New Dimension Sensitive Property for Cellular Automata -- Captive Cellular Automata -- Simulating 3D Cellular Automata with 2D Cellular Automata -- Graph Exploration by a Finite Automaton -- Parametrized and Kolmogorov Complexity -- On Polynomially Time Bounded Symmetry of Information -- Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets -- A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs -- Polynomial Time Approximation Schemes and Parameterized Complexity -- Semantics -- Epistemic Foundation of the Well-Founded Semantics over Bilattices -- Structural Model Checking for Communicating Hierarchical Machines -- Compositional Verification: Decidability Issues Using Graph Substitutions -- Event Structures for Resolvable Conflict -- Scheduling -- Optimal Preemptive Scheduling for General Target Functions -- The Price of Anarchy for Polynomial Social Cost -- Agent-Based Information Handling in Large Networks -- Approximating Earliest Arrival Flows with Flow-Dependent Transit Times -- Algebraic Theory of Languages -- A Hierarchy of Irreducible Sofic Shifts -- Membership and Reachability Problems for Row-Monomial Transformations -- On Pseudovarieties of Semiring Homomorphisms -- An Algebraic Generalization of?-Regular Languages -- Games -- A Protocol for Serializing Unique Strategies -- A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games -- When Can You Play Positionally? -- Languages -- The Dual of Concatenation -- Computational Aspects of Disjunctive Sequences -- Decidability of Trajectory-Based Equations -- Geometry -- Efficient View Point Selection for Silhouettes of Convex Polyhedra -- Angles and Lengths in Reconfigurations of Polygons and Polyhedra -- Improved Bounds and Schemes for the Declustering Problem -- Crossing Number Is Hard for Cubic Graphs -- Languages and Complexity -- A Reducibility for the Dot-Depth Hierarchy -- Sublogarithmic Ambiguity -- An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx -- A Generalization of Repetition Threshold -- Quantum Computing -- An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation -- Universal Test for Quantum One-Way Permutations -- A Common Algebraic Description for Probabilistic and Quantum Computations -- XML -- Extraction and Implication of Path Constraints -- Schema Evolution for XML: A Consistency-Preserving Approach -- Complexity of Decision Problems for Simple Regular Expressions.

Powered by Koha