Fundamentals of Computation Theory [electronic resource] : 11th International Symposium, FCT '97, Krakow, Poland, September 1-3, 1997. Proceedings / edited by Bogdan S. Chlebus, Ludwik Czaja.

1st ed. 1997.
Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1997.
Computer Science (Springer-11645)
Lecture notes in computer science 0302-9743 ; 1279
Lecture Notes in Computer Science, 0302-9743 ; 1279
1 online resource (XII, 484 pages)
Computer science-Mathematics.
Computer graphics.
Data structures (Computer science).
Local subjects:
Theory of Computation. (search)
Discrete Mathematics in Computer Science. (search)
Computer Graphics. (search)
Data Structures. (search)
System Details:
text file PDF
This book constitutes the refereed proceedings of the 11th International Symposium on Fundamentals of Computer Theory, FCT'97, held in Krakow, Poland, in September 1997. The 34 revised full papers presented in the volume were selected from a total of 72 submissions. Also included are six invited papers by leading scientists. The papers address a variety of current topics in theoretical computer science including models of computation, concurrency, algorithms, complexity theory, programming theory, formal languages, graph theory and discrete mathematics, networking, automata theory, term rewriting, et cetera.
The complexity class ? p 2 : Recent results and applications in AI and modal logic
Proof systems for structured algebraic specifications: An overview
Average-case analysis via incompressibility
Locally computable enumerations
The complexity of error-correcting codes
Stochastic analysis of dynamic processes
k-k Sorting on the multi-mesh
Refinement of coloured petri nets
Stratified petri nets
Distributed acyclic orientation of asynchronous anonymous networks
Generalized rational relations and their logical definability
A note on broadcasting with linearly bounded transmission faults in constant degree networks
Logics which capture complexity classes over the reals
Criteria to disprove context-freeness of collage languages
The subword complexity of fixed points of binary uniform morphisms
Efficient parallel computing with memory faults
Bounded concurrency
Concerning the time bounds of existing shortest watchman route algorithms
Query order in the polynomial hierarchy
Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
Pattern-matching problems for 2-dimensional images described by finite automata
The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups
Contextual grammars with distributed catenation and shuffle
A two-dimensional hierarchy for attributed tree transducers
Synchronization of 1-way connected processors
A linear-time heuristic for minimum rectangular coverings (Extended abstract)
On occurrence net semantics for petri nets with contacts
Cellular automata universality revisited
Trade-off results for connection management
On the average complexity of the membership problem for a generalized Dyck language
Towards optimal locality in mesh-indexings
On the hierarchy of nondeterministic branching k-programs
FDT is undecidable for finitely presented monoids with solvable word problems
The equivalence of pebbles and sensing heads for finite automata
From finite automata toward hybrid systems (Extended abstract)
On an optimal quantified propositional proof system nal proof system and a complete language for NP ? co-NP for NP ? co-NP
Lower bounds in on-line geometric searching metric searching
The complexity of universal text-learners
Unique normal forms for nonlinear term rewriting systems: Root overlaps
Behavioural characterizations of partial order logics.
Chlebus, Bogdan S. editor., Editor,
Czaja, Ludwik. editor., Editor,
SpringerLink (Online service)
Contained In:
Springer eBooks
Other format:
Printed edition:
Printed edition:
Publisher Number:
10.1007/BFb0036167 doi
Access Restriction:
Restricted for use by site license.
Location Notes Your Loan Policy
Description Status Barcode Your Loan Policy