LEADER 05855nam 22008415 450 001 9910768448903321 005 20250609110047.0 010 $a3-540-74240-9 024 7 $a10.1007/978-3-540-74240-1 035 $a(CKB)1000000000490591 035 $a(SSID)ssj0000317847 035 $a(PQKBManifestationID)11248533 035 $a(PQKBTitleCode)TC0000317847 035 $a(PQKBWorkID)10294628 035 $a(PQKB)10750433 035 $a(DE-He213)978-3-540-74240-1 035 $a(MiAaPQ)EBC3063380 035 $a(MiAaPQ)EBC6691662 035 $a(Au-PeEL)EBL6691662 035 $a(PPN)12316432X 035 $a(MiAaPQ)EBC337276 035 $a(BIP)32374308 035 $a(BIP)14239239 035 $a(EXLCZ)991000000000490591 100 $a20100301d2007 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aFundamentals of Computation Theory $e16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings /$fedited by Erzsébet Csuhaj-Varjú, Zoltán Ésik 205 $a1st ed. 2007. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2007. 215 $a1 online resource (XIV, 510 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4639 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-540-74239-5 320 $aIncludes bibliographical references and index. 327 $aInvited Lectures -- Rewriting Systems with Data -- Spiking Neural P Systems: Some Characterizations -- Approximating Graphs by Graphs and Functions (Abstract) -- Traces, Feedback, and the Geometry of Computation (Abstract) -- Contributions -- A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings -- Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs -- A Novel Information Transmission Problem and Its Optimal Solution -- Local Testing of Message Sequence Charts Is Difficult -- On Notions of Regularity for Data Languages -- FJMIP: A Calculus for a Modular Object Initialization -- Top-Down Deterministic Parsing of Languages Generated by CD Grammar Systems -- The Complexity of Membership Problems for Circuits over Sets of Positive Numbers -- Pattern Matching in Protein-Protein Interaction Graphs -- From Micro to Macro: How the Overlap Graph Determines the Reduction Graph in Ciliates -- A String-Based Model for Simple Gene Assembly -- On the Computational Power of Genetic Gates with Interleaving Semantics: The Power of Inhibition and Degradation -- On Block-Wise Symmetric Signatures for Matchgates -- Path Algorithms on Regular Graphs -- Factorization of Fuzzy Automata -- Factorisation Forests for Infinite Words -- Marked Systems and Circular Splicing -- The Quantum Query Complexity of Algebraic Properties -- On the Topological Complexity of Weakly Recognizable Tree Languages -- Productivity of Stream Definitions -- Multi-dimensional Packing with Conflicts -- On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time -- Efficient Parameterized Preprocessing for Cluster Editing -- Representing the Boolean OR Function by Quadratic Polynomials Modulo 6 -- On the Complexity of Kings -- Notions of Hyperbolicity in Monoids -- P Systems with Adjoining Controlled Communication Rules -- The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable -- Real-Time Reversible Iterative Arrays -- The Computational Complexity of Monotonicity in Probabilistic Networks -- Impossibility Results on Weakly Black-Box Hardness Amplification -- Maximal and Minimal Scattered Context Rewriting -- Strictly Deterministic CD-Systems of Restarting Automata -- Product Rules in Semidefinite Programming -- Expressive Power of LL(k) Boolean Grammars -- Complexity of Pebble Tree-Walking Automata -- Some Complexity Results for Prefix Gröbner Bases in Free Monoid Rings -- Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs -- An O(1.787 n )-Time Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes. 330 $aThis book features the refereed proceedings of the 16th International Symposium on Fundamentals of Computation Theory. Thirty-nine full papers are presented along with four invited papers. The papers address all current topics in computation theory, including automata and formal languages, design and analysis of algorithms, computational and structural complexity, semantics, logic, circuits and networks, learning theory, and more. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4639 606 $aComputer science 606 $aAlgorithms 606 $aMachine theory 606 $aComputer graphics 606 $aComputer science?Mathematics 606 $aDiscrete mathematics 606 $aTheory of Computation 606 $aAlgorithms 606 $aFormal Languages and Automata Theory 606 $aComputer Graphics 606 $aDiscrete Mathematics in Computer Science 615 0$aComputer science. 615 0$aAlgorithms. 615 0$aMachine theory. 615 0$aComputer graphics. 615 0$aComputer science?Mathematics. 615 0$aDiscrete mathematics. 615 14$aTheory of Computation. 615 24$aAlgorithms. 615 24$aFormal Languages and Automata Theory. 615 24$aComputer Graphics. 615 24$aDiscrete Mathematics in Computer Science. 676 $a004 702 $aE?sik$b Zolta?n$f1951- 702 $aCsuhaj-Varju?$b E. 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910768448903321 996 $aFundamentals of Computation Theory$92557870 997 $aUNINA