Mathematical Foundations of Computer Science 2000: 25th International Symposium, MFCS 2000 Bratislava, Slovakia, August 28 - September 1, 2000 ProceedingsMogens 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
1 | |
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 |
709 | |
Outras edições - Ver todos
Mathematical Foundations of Computer Science 2000: 25th International ... Mogens Nielsen Visualização parcial - 2000 |
Mathematical Foundations of Computer Science 2000: 25th International ... Mogens Nielsen Prévia não disponível - 2000 |
Termos e frases comuns
Abstract algebra algorithm assignment automaton axioms Berlin Heidelberg 2000 binary bisimulation Boolean functions branching programs calculus codes color complexity classes consider construction contains corresponding decision problem defined Definition denote deterministic edge equations equivalent example exists exponential finite set first-order formula given grammar graph G Hence hierarchy infinite input integer interactive interactive machine iteration labeling scheme labelled transition system language layout Lemma linear LNCS lower bound MFCS modal modal logic monoid monotonic functions morphism nodes nondeterministic normal form NP-complete NP-hard OBDDs obtained operation optimal output paper path permutation planar graphs polynomial polynomial-time prefix problem Proc proof properties Proposition prove reachable recursive reduction regular expressions relation result Rovan Eds satisfies second-order logic semantics sequence structure subset symbol temporal logics Theorem theory transition system tree Turing machines variables vertex vertices word