Conference 
Symposium on Mathematical Foundations of Computer Science (1972 ) (29th : 2004 : Prague, Czech Republic)

Series 
Lecture notes in computer science ; 3153. 

Lecture notes in computer science ;
3153.

Subject 
Computer science  Mathematics  Congresses.

Alt Name 
Fiala, Jiří, 1973


Kratochvíl, Jan.


Koubek, Václav.


Ohio Library and Information Network.


LINK (Online service)

Description 
1 online resource (xiv, 902 pages) : illustrations. 

monochrome rdacc 
Note 
Title from title screen (viewed Aug. 12, 2004). 

Print version originally published 2004. 

Electronic book available via Springer Link. 
Bibliography Note 
Includes bibliographical references and index 
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 FixedParameter Algorithms  PRAMOnChip: A Quest for NotSoObvious Nonobviousness  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 BoundedGenus Graphs  Parallel KnockOut 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 2SATDELETION Problem  Graphs and Complexity  Group Coloring and List Group Coloring Are?2 P Complete  Complexity Results in Graph Reconstruction  Generating Paths and Cuts in Multipole (Di)graphs  Packing Directed Cycles Efficiently  Circuits  The Complexity of Membership Problems for Circuits over Sets of Integers  Some MeetintheMiddle Circuit Lower Bounds  The Enumerability of P Collapses P to NC  On NC1 Boolean Circuit Composition of Noninteractive Perfect ZeroKnowledge  General Complexity  All Superlinear Inverse Schemes Are coNPHard  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 TuringHard 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 WellFounded 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  AgentBased Information Handling in Large Networks  Approximating Earliest Arrival Flows with FlowDependent Transit Times  Algebraic Theory of Languages  A Hierarchy of Irreducible Sofic Shifts  Membership and Reachability Problems for RowMonomial 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 TrajectoryBased 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 DotDepth Hierarchy  Sublogarithmic Ambiguity  An Elementary Proof for the Nonparametrizability 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 OneWay Permutations  A Common Algebraic Description for Probabilistic and Quantum Computations  XML  Extraction and Implication of Path Constraints  Schema Evolution for XML: A ConsistencyPreserving Approach  Complexity of Decision Problems for Simple Regular Expressions. 
Access 
Available to OhioLINK libraries 
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. 
Reproduction 
Electronic reproduction. Columbus, OH : OhioLINK, 2008. 
System Details 
Mode of access: World Wide Web 
ISBN 
3540228233 (pbk.) 

9783540228233 (pbk.) 
OCLC # 
664271777 
Link 
OhioLINK electronic book center (OCoLC)180989150. 

SpringerLink (OCoLC)43927870. 
Additional Format 
Print version: Symposium on Mathematical Foundations of Computer Science (1972 ) (29th : 2004 : Prague, Czech Republic). Mathematical foundations of computer science 2004. Berlin : Springer, 2004 3540228233 (DLC) 2004109757 (OCoLC)56334025. 
