Mathematical foundations of computer science 1995 : 20th International Symposium, MFCS '95 Prague, Czech Republic, August 28 September 1, 1995 : proceedings
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 a...
Enregistré dans:
| Collectivité auteur: | |
|---|---|
| Autres auteurs: | , |
| Format: | Livre numérique |
| Langue: | Anglais |
| Publié: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Collection: | Lecture notes in computer science
969 |
| Sujets: | |
| Accès en ligne: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Note: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Mathematical foundations of computer science 1995, 20th International Symposium, MFCS '95, Prague, Czech Republic, August 28-September 1, 1995, proceedings, Jiří Wiedermann, Petr Hájek, eds, Berlin, Springer, 1995, 1 vol. (XIII-588 p.), Lecture notes in computer science, 3-540-60246-1 • Mathematical Foundations of Computer Science 1995, Texte imprimé, 9783662168585 |
Table des matières:
- 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.