Nicht aus der Schweiz? Besuchen Sie lehmanns.de

Mathematical Foundations of Computer Science 1995

20th International Symposium, MFCS'95, Prague, Czech Republic, August 28 - September 1, 1995. Proceedings

Jiri Wiedermann, Petr Hajek (Herausgeber)

Buch | Softcover
XIII, 594 Seiten
1995 | 1995
Springer Berlin (Verlag)
978-3-540-60246-0 (ISBN)

Lese- und Medienproben

Mathematical Foundations of Computer Science 1995 -
CHF 149,75 inkl. MwSt
This book presents the proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science, MFCS'95, held in Prague, Czech Republic in August/September 1995.
The book contains eight invited papers and two abstracts of invited talks by outstanding scientists as well as 44 revised full research papers selected from a total of 104 submissions. All relevant aspects of theoretical computer science are addressed, particularly the mathematical foundations; the papers are organized in sections on structural complexity, algorithms, complexity theory, graphs in models of computation, lower bounds, formal languages, unification, rewriting and type theory, distributed computation, concurrency, semantics, model checking, and formal calculi.

Scheduling parallel communication: The h-relation problem.- Decomposable structures, Boolean function representations, and optimization.- The complexity of interval routing on random graphs.- Bridging across the log(n) space frontier.- Second order logic and the weak exponential hierarchies.- On the computing paradigm and computational complexity.- Ranked structures in nonmonotonic reasoning and belief revision: Abstract.- Symbolic dynamics and finite automata.- Lower bounds for propositional proofs and independence results in bounded arithmetic (abstract).- Physics and the new computation.- Measure on P: Robustness of the notion.- Comparing counting classes for logspace, one-way logspace, and first-order.- Automata that take advice.- Nonuniform lower bounds for exponential time classes.- On a quantitative notion of uniformity.- Separations by random oracles and "Almost" classes for generalized reducibilities.- On the complexity of finite memory policies for Markov decision processes.- Derandomization for sparse approximations and independent sets.- Asymptotically efficient in-place merging.- The complexity of the falsifiability problem for pure implicational formulas.- Strong lower bounds on the approximability of some NPO PB-complete maximization problems.- Some typical properties of large AND/OR Boolean formulas.- The hedge: An efficient storage device for Turing machines with one head.- Graph inference from a walk for trees of bounded degree 3 is NP-complete.- Honeycomb networks.- Witness-isomorphic reductions and the local search problem (extended abstract).- Multiple product modulo arbitrary numbers.- Lower bounds for the majority communication complexity of various graph accessibility problems.- Strong optimal lower bounds for Turing machines that acceptnonregular languages.- A superpolynomial lower bound for (1,+k(n))-branching programs.- Deterministic parsing for augmented context-free grammars.- A periodicity theorem on words and applications.- A new approach to analyse Coupled-Context-Free languages.- Computational complexity of simultaneous elementary matching problems.- Graph reducibility of term rewriting systems.- Positive recursive type assignment.- String recognition on anonymous rings.- The firing squad synchronization problem on Cayley graphs.- Solving cheap graph problems on Meshes.- An elementary bisimulation decision procedure for arbitrary context-free processes.- On congruences and partial orders.- Performance preorder: Ordering processes with respect to speed.- Towards a semantic theory of CML.- Modular constructions of distributing automata.- On the proof method for bisimulation.- Towards a calculus of predicate transformers.- An abstract account of composition.- Syntax and semantics of Procol.- Synthesizing distinguishing formulae for real time systems -extended abstract.- From timed automata to logic - and back.- Incremental model checking for decomposable structures.- Automata for the modal ?-calculus and related results.- A ?-calculus with local views for systems of sequential agents.- An operator calculus approach to the evolution of dynamic data structures.

Erscheint lt. Verlag 16.8.1995
Reihe/Serie Lecture Notes in Computer Science
Zusatzinfo XIII, 594 p.
Verlagsort Berlin
Sprache englisch
Maße 155 x 233 mm
Gewicht 807 g
Themenwelt Informatik Theorie / Studium Algorithmen
Informatik Theorie / Studium Compilerbau
Schlagworte algorithm • Algorithm analysis and problem complexity • Algorithmen • Algorithmentheorie • algorithms • Algorithms Theory • Algorithmus • Complexity • Complexity theory • formal language • Foundaations of Computer Science • Graph • Graphentheorie • graph theory • Hardcover, Softcover / Informatik, EDV/Informatik • HC/Informatik, EDV/Informatik • Informatik • Informatikgrundlagen • Komplexität • Komplexitätstheorie • Mathematische Logik • Model Checking • Programmiersemantik • Programmiersprache • Programming Semantics • Semantics
ISBN-10 3-540-60246-1 / 3540602461
ISBN-13 978-3-540-60246-0 / 9783540602460
Zustand Neuware
Haben Sie eine Frage zum Produkt?
Mehr entdecken
aus dem Bereich
Interlingua zur Gewährleistung semantischer Interoperabilität in der …

von Josef Ingenerf; Cora Drenkhahn

Buch | Softcover (2023)
Springer Fachmedien (Verlag)
CHF 46,15