| |
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNISA996465726903316 |
|
|
Titolo |
Fundamentals of Computation Theory [[electronic resource] ] : International Conference FCT '89, Szeged, Hungary, August 21-25, 1989. Proceedings / / edited by Janos Csirik, Ferenc Gecseg, Janos Demetrovics |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1989 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Edizione |
[1st ed. 1989.] |
|
|
|
|
|
Descrizione fisica |
|
1 online resource (XIV, 498 p.) |
|
|
|
|
|
|
Collana |
|
Lecture Notes in Computer Science, , 0302-9743 ; ; 380 |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Computers |
Algorithms |
Computer logic |
Mathematical logic |
Microprogramming |
Combinatorics |
Computation by Abstract Devices |
Algorithm Analysis and Problem Complexity |
Logics and Meanings of Programs |
Mathematical Logic and Formal Languages |
Control Structures and Microprogramming |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
Bibliographic Level Mode of Issuance: Monograph |
|
|
|
|
|
|
Nota di contenuto |
|
On word equations and Makanin's algorithm -- Complexity classes with complete problems between P and NP-C -- Interpretations of synchronous flowchart schemes -- Generalized Boolean hierarchies and Boolean hierarchies over RP -- The equational logic of iterative processes -- The distributed bit complexity of the ring: From the anonymous to the non-anonymous case -- The jump number problem for biconvex graphs and rectangle covers of rectangular regions -- Recent developments in the design of asynchronous circuits -- New simulations between CRCW PRAMs -- About connections between syntactical and computational complexity -- Completeness in |
|
|
|
|
|
|
|
|
|
|
|
approximation classes -- Separating completely complexity classes related to polynomial size ?-Decision trees -- On product hierarchies of automata -- On the communication complexity of planarity -- Context-free NCE graph grammars -- Dynamic data structures with finite population: A combinatorial analysis -- Iterated deterministic top-down look-ahead -- Using generating functions to compute concurrency -- A logic for nondeterministic functional programs extended abstract -- Decision problems and Coxeter groups -- Complexity of formula classes in first order logic with functions -- Normal and sinkless Petri nets -- Descriptive and computational complexity -- The effect of null-chains on the complexity of contact schemes -- Monte-Carlo inference and its relations to reliable frequency identification -- Semilinear real-time systolic trellis automata -- Inducibility of the composition of frontier-to-root tree transformations -- On oblivious branching programs of linear length -- Some time-space bounds for one-tape deterministic turing machines -- Rank of rational finitely generated W-languages -- Extensional properties of sets of time bounded complexity (extended abstract) -- Learning under uniform distribution -- An extended framework for default reasoning -- Logic programming of some mathematical paradoxes -- Analysis of compact 0-complete trees: A new access method to large databases -- Representation of recursively enumerable languages using alternating finite tree recognizers -- About a family of binary morphisms which stationary words are Sturmian -- On the finite degree of ambiguity of finite tree automata -- Approximation algorithms for channel assignment in cellular radio networks -- The Borel hierarchy is infinite in the class of regular sets of trees -- Parallel general prefix computations with geometric, algebraic and other applications -- Kolmogorov complexity and Hausdorff dimension -- Tree language problems in pattern recognition theory -- The computational complexity of cellular automata -- On restricted Boolean circuits -- The complexity of connectivity problems on context-free graph languages -- Constructivity, computability, and computational complexity in analysis. |
|
|
|
|
|
|
Sommario/riassunto |
|
This volume contains the proceedings of the conference on Fundamentals of Computation Theory held in Szeged, Hungary, August 21-25, 1989. The conference is the seventh in the series of the FCT conferences initiated in 1977 in Poznan-Kornik, Poland. The papers collected in this volume are the texts of invited contributions and shorter communications falling into one of the following sections: - Efficient Computation by Abstract Devices: Automata, Computability, Probabilistic Computations, Parallel and Distributed Computing; - Logics and Meanings of Programs: Algebraic and Categorical Approaches to Semantics, Computational Logic, Logic Programming, Verification, Program Transformations, Functional Programming; - Formal Languages: Rewriting Systems, Algebraic Language Theory; - Computational Complexity: Analysis and Complexity of Algorithms, Design of Efficient Algorithms, Algorithms and Data Structures, Computational Geometry, Complexity Classes and Hierarchies, Lower Bounds. |
|
|
|
|
|
|
|
| |