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

Capa
Springer Science & Business Media, 14 de ago de 2000 - 710 páginas
This volume contains papers selected for presentation at the Silver Jubilee 25th Symposium on Mathematical Foundations of Computer Science | MFCS 2000, held in Bratislava, Slovakia, August 28 { September 1, 2000. MFCS 2000 was organized under the auspices of the Minister of Education of the Slovak Republic, Milan Ft a cnik, by the Slovak Society for Computer Science, and the Comenius University in Bratislava, in cooperation with other institu- ons in Slovakia. It was supported by the European Association for Theoretical Computer Science, the European Research Consortium for Informatics and - thematics, and the Slovak Research Consortium for Informatics and Mathe- tics. The series of MFCS symposia, organized alternately in the Czech Republic, Poland, and Slovakia since 1972, has a well-established tradition. The MFCS symposia encourage high-quality research in all branches of theoretical computer science. Their broad scope provides an opportunity of bringing together spec- lists who do not usually meet at specialized conferences. The previous meetings took place in Jablonna, 1972; Strbsk e Pleso, 1973; Jadwisin, 1974; Mari ansk e L azn e, 1975; Gdansk, 1976; Tatransk a Lomnica, 1977; Zakopane, 1978; Olomouc, 1979; Rydzina, 1980; Strbsk e Pleso, 1981; Prague, 1984; Bratislava, 1986; C- lsbad, 1988; Porabk a-Kozubnik, 1989; Bansk a Bystrica, 1990; Kazimierz Dolny, 1991; Prague, 1992; Gdansk, 1993, Ko sice, 1994; Prague, 1995; Krak ow, 1996; Bratislava, 1997; Brno, 1998; and Szklarska Poreba, 1999.
 

O que estão dizendo - Escrever uma resenha

Não encontramos nenhuma resenha nos lugares comuns.

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 - Visualizar todos

Termos e frases comuns

Informações bibliográficas