Borrow it
Coverart for item
The Resource Mathematical Foundations of Computer Science 1995 : 20th International Symposium, MFCS '95 Prague, Czech Republic, August 28-September 1, 1995 Proceedings, edited by Jiří Wiedermann, Petr Hájek

Mathematical Foundations of Computer Science 1995 : 20th International Symposium, MFCS '95 Prague, Czech Republic, August 28-September 1, 1995 Proceedings, edited by Jiří Wiedermann, Petr Hájek

Creator
Contributor
Summary
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
Language
eng
Work
Publication
Extent
1 online resource
Contents
  • 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 accept nonregular 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
Isbn
9783540447689
Instance
Label
Mathematical Foundations of Computer Science 1995 : 20th International Symposium, MFCS '95 Prague, Czech Republic, August 28-September 1, 1995 Proceedings
Title
Mathematical Foundations of Computer Science 1995
Title remainder
20th International Symposium, MFCS '95 Prague, Czech Republic, August 28-September 1, 1995 Proceedings
Statement of responsibility
edited by Jiří Wiedermann, Petr Hájek
Creator
Contributor
Subject
Language
eng
Summary
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
Member of
Cataloging source
KIJ
http://library.link/vocab/creatorName
Wiedermann, J.
Dewey number
004.0151
Image bit depth
0
Index
index present
LC call number
QA76.9.M35
LC item number
M38 1995
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorDate
1995
http://library.link/vocab/relatedWorkOrContributorName
  • Hájek, Petr
  • Symposium on Mathematical Foundations of Computer Science (1972- )
Series statement
Lecture Notes in Computer Science,
Series volume
969
http://library.link/vocab/subjectName
  • Computer science
  • Software engineering
  • Computer software
  • Logic design
  • Computer science
  • Computer software
  • Logic design
  • Software engineering
  • Computer Science
  • Engineering & Applied Sciences
Label
Mathematical Foundations of Computer Science 1995 : 20th International Symposium, MFCS '95 Prague, Czech Republic, August 28-September 1, 1995 Proceedings, edited by Jiří Wiedermann, Petr Hájek
Instantiates
Publication
Antecedent source
mixed
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
not applicable
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
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 accept nonregular 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
Control code
827359994
Dimensions
unknown
Extent
1 online resource
File format
multiple file formats
Form of item
online
Isbn
9783540447689
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/3-540-60246-1
Other physical details
volumes: digital.
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
(OCoLC)827359994
Label
Mathematical Foundations of Computer Science 1995 : 20th International Symposium, MFCS '95 Prague, Czech Republic, August 28-September 1, 1995 Proceedings, edited by Jiří Wiedermann, Petr Hájek
Publication
Antecedent source
mixed
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
not applicable
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
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 accept nonregular 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
Control code
827359994
Dimensions
unknown
Extent
1 online resource
File format
multiple file formats
Form of item
online
Isbn
9783540447689
Level of compression
uncompressed
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/3-540-60246-1
Other physical details
volumes: digital.
Quality assurance targets
absent
Reformatting quality
access
Specific material designation
remote
System control number
(OCoLC)827359994

Subject

Member of

Library Locations

    • Ellis LibraryBorrow it
      1020 Lowry Street, Columbia, MO, 65201, US
      38.944491 -92.326012

Library Links

Structured data from the Bibframe namespace is licensed under the Creative Commons Attribution 4.0 International License by University of Missouri Libraries. Additional terms may apply to data associated with third party namespaces.
Processing Feedback ...