Fundamentals of Computation Theory
Springer Berlin (Verlag)
978-3-540-51498-5 (ISBN)
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 (extendedabstract).- 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.
| Erscheint lt. Verlag | 31.7.1989 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | XIV, 498 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 216 x 279 mm |
| Gewicht | 712 g |
| Themenwelt | Informatik ► Software Entwicklung ► User Interfaces (HCI) |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| Schlagworte | Algorithm analysis and problem complexity • algorithms • Automata • Calculus • combinatorics • Complexity • Computability • Computational Complexity • distributed programming • Efficient Algorithms • Effiziente Algorithmen • Formale Sprachtheorie • formal language • Formal Languages • Formal Language Theory • Grammars • Komplexität • Logic • Parallelprogrammierung • Parallel Programming • Petri net • Programmiertechniken • Programming Techniques • Program Transformation • RP • Semantics • turing degree • Turing Machine |
| ISBN-10 | 3-540-51498-8 / 3540514988 |
| ISBN-13 | 978-3-540-51498-5 / 9783540514985 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
