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.
Author(s): Marek Karpinski (auth.), Gabriel Ciobanu, Gheorghe Păun (eds.)
Series: Lecture Notes in Computer Science 1684
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1999
Language: English
Pages: 576
Tags: Theory of Computation; Discrete Mathematics in Computer Science; Data Structures
Randomized complexity of linear arrangements and polyhedra?....Pages 1-12
Tile transition systems as structured coalgebras?....Pages 13-38
Caesar and DNA — views on cryptology....Pages 39-53
Automata and their interaction: Definitional suggestions....Pages 54-89
Axiomatising asynchronous process calculi....Pages 90-90
A polynomial time approximation scheme for dense MupIN 2 S{upAT} ....Pages 91-99
Decidable classes of the verification problem in a timed predicate logic....Pages 100-111
Interpretations of extensible objects and types....Pages 112-123
Restrictive acceptance suffices for equivalence problems....Pages 124-135
Grammar systems as language analyzers and recursively enumerable languages....Pages 136-147
An interpretation of extensible objects....Pages 148-160
Modeling operating systems schedulers with multi-stack-queue grammars....Pages 161-172
Iterative arrays with a wee bit alternation....Pages 173-184
Secret sharing schemes with detection of cheaters for a general access structure....Pages 185-194
Constructive notes on uniform and locally convex spaces....Pages 195-203
Graph automorphisms with maximal projection distances....Pages 204-214
Kleene theorems for event-clock automata....Pages 215-225
Strong iteration lemmata for regular, linear, context-free, and linear indexed languages....Pages 226-233
Exponential output size of top-down tree transducers....Pages 234-245
On recognizable languages in divisibility monoids....Pages 246-257
Expressiveness of point-to-point versus broadcast communications....Pages 258-268
On relative loss bounds in generalized linear regression....Pages 269-280
Generalized P-systems....Pages 281-292
Optimal, distributed decision-making: The case of no communication....Pages 293-303
Generalized PCP is decidable for marked morphisms....Pages 304-315
On time-constructible functions in one-dimensional cellular automata....Pages 316-326
Dichotomy theorem for the generalized unique satisfiability problem....Pages 327-337
A general categorical connection between local event structures and local traces....Pages 338-349
Correct translation of mutually recursive function systems into TOL collage grammars....Pages 350-361
Synchronized product of linear bounded machines....Pages 362-373
On maximal repetitions in words....Pages 374-385
Axiomatization of the coherence property for categories of symmetries....Pages 386-397
Sewing grammars....Pages 398-408
State and transition complexity of Watson-Crick finite automata....Pages 409-420
A confluence result for a typed λ-calculus of exception handling with fixed-point....Pages 421-432
δ -Uniformly decidable sets and turing machines....Pages 433-440
A parallel context-free derivation hierarchy....Pages 441-450
Generalized synchronization languages....Pages 451-462
A generalization of Dijkstra’s calculus to typed program specifications....Pages 463-474
Homomorphisms and concurrent term rewriting....Pages 475-487
On two-sided infinite fixed points of morphisms....Pages 488-499
Tiling multi-dimensional arrays....Pages 500-511
Modeling interaction by sheaves and geometric logic....Pages 512-523
The operators minCh and maxCh on the polynomial hierarchy....Pages 524-535
The Kolmogorov complexity of real numbers....Pages 536-546
A partial order method for the verification of time Petri nets....Pages 547-558
Deriving formulas for domination numbers of fasciagraphs and rotagraphs....Pages 559-568
