LEADER 06524nam 22006495 450 001 9910144917503321 005 20200702033939.0 010 $a3-540-69547-8 024 7 $a10.1007/BFb0029943 035 $a(CKB)1000000000234704 035 $a(SSID)ssj0000324667 035 $a(PQKBManifestationID)11224809 035 $a(PQKBTitleCode)TC0000324667 035 $a(PQKBWorkID)10314786 035 $a(PQKB)10750811 035 $a(DE-He213)978-3-540-69547-9 035 $a(PPN)15517942X 035 $a(EXLCZ)991000000000234704 100 $a20121227d1997 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aMathematical Foundations of Computer Science 1997$b[electronic resource] $e22nd International Symposium, MFCS'97, Bratislava, Slovakia, August 25-29, 1997, Proceedings /$fedited by Igor Privara, Peter Ruzicka 205 $a1st ed. 1997. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d1997. 215 $a1 online resource (X, 526 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v1295 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-63437-1 327 $aGame semantics for programming languages -- Communication complexity -- Treewidth: Algorithmic techniques and results -- When are two rewrite systems more than none? -- Positive applications of lattices to cryptography -- A tile-based coordination view of asynchronous ?-calculus -- Communication complexity and sequential computation -- Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus -- Computational limitations of Stochastic Turing machines and Arthur-Merlin games with small space bounds -- Learning to perform knowledge-intensive inferences -- Resolution proofs, exponential bounds, and Kolmogorov complexity -- The expressiveness of Datalog cicuits (DAC) -- The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes -- A category of transition systems and its relations with orthomodular posets -- Accepting Zeno words without making time stand still -- Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams -- Specifying computations using hyper transition systems -- A shift-invariant metric on S zz inducing a non-trivial topology -- Subtyping calculus of construction (extended abstract) -- Distances between languages and reflexivity of relations -- Partial characterization of synchronization languages -- Integrating the specification techniques of graph transformation and temporal logic -- On the generation of trees by hyperedge replacement -- Regulation by valences -- Simulation as a correct transformation of rewrite systems -- On the dilation of interval routing -- Relating conflict-free stable transition and event models (extended abstract) -- The giant component threshold for random regular graphs with edge faults -- A topological generalization of propositional linear time temporal logic -- Multi-head finite automata: Data-independent versus data-dependent computations -- Complexity of finding short resolution proofs -- On P versus NP?co-NP for decision trees and read-once branching programs -- A characterization of abstract families of algebraic power series -- Repetitiveness of D0L-languages is decidable in polynomial time -- Minimal letter frequency in n-th power-free binary words -- Real-time generation of primes by a one-dimensional cellular automaton with 11 states -- Optimal algorithms for complete linkage clustering in d dimensions -- Invertible linear cellular automata over Zm: Algorithmic and dynamical aspects -- Two-level contextual grammars: The internal case -- Counting problems over the reals -- On the influence of the state encoding on OBDD-representations of finite state machines -- Decomposition of TrPTL formulas -- NP-hard sets have many hard instances -- Deciding verbose languages with linear advice -- Homomorphic images of sentential forms and terminating grammars (extended abstract) -- Simplification orders for term graph rewriting -- Dependency-based action refinement -- A hierarchy for (1, +k)-branching programs with respect to k -- Routing with finite speeds of memory and network -- Queries and algorithms computable by polynomial time existential reflective machines -- Partial order semantics and read arcs. 330 $aThis book constitutes the refereed proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS '97, held in Bratislava, Slovakia, in August 1997. The 40 revised full papers presented were carefully selected from a total of 94 submissions. Also included are nine invited papers and two abstracts of invited talks. The papers cover the whole range of theoretical computer science including programming theory, complexity theory, mathematical logic, rewriting, grammars, formal languages, theory of algorithms, computational graph theory, etc. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v1295 606 $aComputers 606 $aProgramming languages (Electronic computers) 606 $aSoftware engineering 606 $aComputer science?Mathematics 606 $aTheory of Computation$3https://scigraph.springernature.com/ontologies/product-market-codes/I16005 606 $aProgramming Languages, Compilers, Interpreters$3https://scigraph.springernature.com/ontologies/product-market-codes/I14037 606 $aSoftware Engineering$3https://scigraph.springernature.com/ontologies/product-market-codes/I14029 606 $aDiscrete Mathematics in Computer Science$3https://scigraph.springernature.com/ontologies/product-market-codes/I17028 615 0$aComputers. 615 0$aProgramming languages (Electronic computers). 615 0$aSoftware engineering. 615 0$aComputer science?Mathematics. 615 14$aTheory of Computation. 615 24$aProgramming Languages, Compilers, Interpreters. 615 24$aSoftware Engineering. 615 24$aDiscrete Mathematics in Computer Science. 676 $a004.0151 702 $aPrivara$b Igor$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aRuzicka$b Peter$4edt$4http://id.loc.gov/vocabulary/relators/edt 906 $aBOOK 912 $a9910144917503321 996 $aMathematical Foundations of Computer Science 1997$92257563 997 $aUNINA