Fundamentals of Computation Theory: 12th International Symposium, Fct'99, Iasi, Romania, August 30-September 3, 1999 : Porceedings

by Ciobanu, Gabriel; Ciobanu, Gabriel; Paun, Gheorghe

• ISBN13: 9783540664123
• ISBN10: 3540664122
• Format: Paperback
• Copyright: 1999-09-01
• Publisher: Springer Verlag

Summary

This book constitutes the refereed proceedings of the 12th International Symposium on Fundamentals of Computation Theory, FCT '99, held in Iasi, Romania in August/September 1999.The 42 revised full papers presented together with four invited papers were carefully selected from a total of 102 submissions. Among the topics addressed are abstract data types, algorithms and data structures, automata and formal languages, categorical and topological approaches, complexity, computational geometry, concurrency, cryptology, distributed computing, logics in computer science, process algebras, symbolic computation, molecular computing, quantum computing, etc.

Table of Contents

Invited Lectures
Randomized Complexity of Linear Arrangements and Polyhedra	1	(12)
M. Karpinski
Tile Transition Systems as Structured Coalgebras	13	(26)
A. Corradini
R. Heckel
U. Montanari
Caesar and DNA. Views on Cryptology	39	(15)
A. Salomaa
Automata and Their Interaction: Definitional Suggestions	54	(36)
B. A. Trakhtenbrot
Axiomatising Asynchronous Process Calculi	90	(1)
M. Hennessy
Technical Contributions
A Polynomial Time Approximation Scheme for Dense Min 2Sat	91	(9)
C. Bazgan
W. Fernandez de la Vega
Decidable Classes of the Verification Problem in a Timed Predicate Logic	100	(12)
D. Beauquier
A. Slissenko
Interpretations of Extensible Objects and Types	112	(12)
V. Bono
M. Bugliesi
Restrictive Acceptance Suffices for Equivalence Problems	124	(12)
B. Borchert
L.A. Hemaspaandra
J. Rothe
Grammar Systems as Language Analyzers and Recursively Enumerable Languages	136	(12)
H. Bordihn
J. Dassow
G. Vaszil
An Interpretation of Extensible Objects	148	(13)
G. Boudol
S. Dal-Zilio
Modeling Operating Systems Schedulers with Multi-Stack-Queue Grammars	161	(12)
L. Breveglieri
S. Crespi Reghizzi
A. Cherubini
Iterative Arrays with a Wee Bit Alternation	173	(12)
T. Buchholz
A. Klein
M. Kutrib
Secret Sharing Schemes with Detection of Cheaters for a General Access Structure	185	(10)
S. Cabello
C. Padro
G. Saez
Constructive Notes on Uniform and Locally Convex Spaces	195	(9)
L. Dediu
D. Bridges
Graph Automorphisms with Maximal Projection Distances	204	(11)
H.N. de Ridder
H.L. Bodlaender
Kleene Theorems for Event-Clock Automata	215	(11)
C. Dima
Strong Iteration Lemmata for Regular, Linear, Context-Free, and Linear Indexed Languages	226	(8)
P. Domosi
M. Kudlek
Exponential Output Size of Top-Down Tree Transducers	234	(12)
F. Drewes
On Recognizable Languages in Divisibility Monoids	246	(12)
M. Droste
D. Kuske
Expressiveness of Point-to-Point versus Broadcast Communications	258	(11)
C. Ene
T. Muntean
On Relative Loss Bounds in Generalized Linear Regression	269	(12)
J. Forster
Generalized P-Systems	281	(12)
R. Freund
Optimal, Distributed Decision-Making: The Case of No Communication	293	(11)
S. Georgiades
M. Mavronicolas
P. Spirakis
Generalized PCP Is Decidable for Marked Morphisms	304	(12)
V. Halava
T. Harju
M. Hirvensalo
On Time-Constructible Functions in One-Dimensional Cellular Automata	316	(11)
C. Iwamoto
T. Hatsuyama
K. Morita
K. Imai
Dichotomy Theorem for the Generalized Unique Satisfiability Problem	327	(11)
L. Juban
A General Categorical Connection between Local Event Structures and Local Traces	338	(12)
H.C.M. Kleijn
R. Morin
B. Rozoy
Correct Translation of Mutually Recursive Function Systems into TOL Collage Grammars	350	(12)
R. Klempien-Hinrichs
H.-J. Kreowski
S. Taubenberger
Synchronized Product of Linear Bounded Machines	362	(12)
T. Knapik
E. Payet
On Maximal Repetitions in Words	374	(12)
R. Kolpakov
G. Kucherov
Axiomatization of the Coherence Property for Categories of Symmetries	386	(12)
D. Lucanu
Sewing Grammars	398	(11)
C. Martin-Vide
A. Mateescu
State and Transition Complexity of Watson-Crick Finite Automata	409	(12)
A. Paun
M. Paun
A Confluence Result for a Typed λ-Calculus of Exception Handling with Fixed-Point	421	(12)
C. Piliere
δ-Uniformly Decidable Sets and Turing Machines	433	(8)
A. Popovici
D. Popovici
A Parallel Context-Free Derivation Hierarchy	441	(10)
K. Reinhardt
Generalized Synchronization Languages	451	(12)
I. Ryl
Y. Roos
M. Clerbout
A Generalization of Dijkstra's Calculus to Typed Program Specifications	463	(12)
K.-D. Schewe
B. Thalheim
Homomorphisms and Concurrent Term Rewriting	475	(13)
F. Seynhaeve
S. Tison
M. Tommasi
On Two-Sided Infinite Fixed Points of Morphisms	488	(12)
J. Shallit
M.-w. Wang
Tiling Multi-dimensional Arrays	500	(12)
J.P. Sharp
Modeling Interaction by Sheaves and Geometric Logic	512	(12)
V. Sofronie-Stokkermans
K. Stokkermans
The Operators minCh and maxCh on the Polynomial Hierarchy	524	(12)
H. Spakowski
J. Vogel
The Kolmogorov Complexity of Real Numbers	536	(11)
L. Staiger
A Partial Order Method for the Verification of Time Petri Nets	547	(12)
I. Virbitskaite
E. Pokozy
Deriving Formulas for Domination Numbers of Fasciagraphs and Rotagraphs	559	(10)
J. Zerovnik
Author Index	569