Mathematical Foundations of Computer Science 2000: 25th International Symposium, MFCS 2000 Bratislava, Slovakia, August 28 - September 1, 2000 Proceedings

Capa
Mogens Nielsen, Branislav Rovan
Springer, 29 de jun. de 2003 - 710 páginas
This book constitutes the refereed proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, MFCS 2000, held in Bratislava/Slovakia in August/September 2000. The 57 revised full papers presented together with eight invited papers were carefully reviewed and selected from a total of 147 submissions. The book gives an excellent overview on current research in theoretical informatics. All relevant foundational issues, from mathematical logics as well as from discrete mathematics are covered. Anybody interested in theoretical computer science or the theory of computing will benefit from this book.
 

Conteúdo

Region Analysis and a Calculus with Groups
1
Abstract Data Types in Computer Algebra
21
What Do We Learn from Experimental Algorithmics
36
AndOr Hierarchies and Round Abstraction
52
Electoral Systems
64
A Survey
84
On Algorithms and Interaction
99
On the Use of Duality and Geometry in Layouts for ATM Networks
114
State Space Reduction Using Partial Confluence
383
Reducing the Number of Solutions of NP Functions
394
Regular Collections of Message Sequence Charts Extended Abstract
405
Alternating and Empty Alternating Auxiliary Stack Automata
415
Decidable Properties and Applications to Verification Problems
426
A Family of NFAs Which Need Deterministic States
436
Applications of Fractional Graph Coloring
446
Matching Modulo Associativity and Idempotency Is NPComplete
456

On the Lower Bounds for OneWay Quantum Automata
132
Axiomatizing Fully Complete Models for ML Polymorphic Types
141
Measure Theoretic Completeness Notions for the Exponential Time Classes
152
EdgeBisection of Chordal Rings
162
Equation Satisfiability and Program Satisfiability for Finite Monoids
172
XML Grammars
182
Simplifying Flow Networks
192
Balanced kColorings
202
A Compositional Model for Confluent Dynamic DataFlow Networks
212
Restricted Nondeterministic ReadOnce Branching Programs and an Exponential Lower Bound for Integer Multiplication Extended Abstract
222
Expressiveness of Updatable Timed Automata
232
Iterative Arrays with Small Time Bounds
243
Embedding Fibonacci Cubes into Hypercubes with Faulty Nodes
253
PeriodicLike Words
264
The Monadic Theory of Morphic Infinite Words and Generalizations
275
Optical Routing of Uniform Instances in Tori
285
Factorizing Codes and Schützenberger Conjectures
295
Compositional Characterizations of Terms Using Intersection Types Extended Abstract
304
Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
314
Subtractive Reductions and Complete Problems for Counting Complexity Classes
323
On the Autoreducibility of Random Sequences
333
Iteration Theories of Boolean Functions
343
An Algorithm Constructing the Semilinear Post for 2Dim ResetTransfer VASS Extended Abstract
353
NPCompleteness Results and Efficient Approximations for Radiocoloring in Planar Graphs
363
Explicit Fusions
373
Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization Extended Abstract
477
Formal Series over Algebras
488
µCalculus Synthesis
497
The Infinite Versions of LogSpace P Are Consistent with the Axioms of Set Theory
508
Timed Automata with Monotonic Activities
518
On a Generalization of BiComplement Reducible Graphs
528
Automatic Graphs and Graph D0LSystems
539
Bilinear Functions and Trees over the Semiring
549
Derivability in Locally Quantified Modal Logics via Translation in Set Theory
559
Calculus Structured Coalgebras and Minimal HDAutomata
569
Informative Labeling Schemes for Graphs Extended Abstract
579
Separation Results for Rebound Automata
589
Unary Pushdown Automata and Auxiliary Space Lower Bounds
599
Binary Decision Diagrams by Shared Rewriting
609
Verifying Single and Multimutator Garbage Collectors with OwickiGries in IsabelleHOL
619
Why so Many Temporal Logics Climb up the Trees?
629
Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems
640
A Hierarchy Result for ReadOnce Branching Programs with Restricted Parity Nondeterminism Extended Abstract
650
On Diving in Trees
660
Abstract Syntax and Variable Binding for Linear Binders
672
Regularity of Congruential Graphs
680
Sublinear Ambiguity
690
An AutomataBased Recognition Algorithm for Semiextended Regular Expressions
699
Author Index
709
Direitos autorais

Outras edições - Ver todos

Termos e frases comuns

Informações bibliográficas