{"entities":{"Q1769767":{"pageid":1780509,"ns":120,"title":"Item:Q1769767","lastrevid":43316671,"modified":"2025-07-24T16:05:49Z","type":"item","id":"Q1769767","labels":{"en":{"language":"en","value":"Mathematical foundations of computer science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22--27, 2004. Proceedings."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2148966"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1769767$ED5C42F6-7395-4712-A876-7FCE1F961408","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"787b1a61c5d25272a957ff3e77a9bf95a237d019","datavalue":{"value":{"text":"Mathematical foundations of computer science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22--27, 2004. Proceedings.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1769767$D12DDD72-917E-428A-A9EE-1F04C08FAE9C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d8dbd5346c009108ed7bdd3ad9ce19c7d6e9092","datavalue":{"value":"1058.68005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1769767$6E9D4B03-89D3-4BF0-8A91-DCCB7FF13A7C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1769767$05E2D1C6-2A0A-4D9A-9176-6004AFFE987D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ef9bbd95a6dd7ae5b43fa2d065daa6fcf276ac4c","datavalue":{"value":{"time":"+2005-03-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1769767$7737CED6-6FCC-415E-8B28-AB6C83B4B480","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5662881f04bc5c6997d8f7b771c28c7a2a39af2f","datavalue":{"value":"The articles of this volume will be reviewed individually. The preceding symposium has been reviewed (see Zbl 1025.00004).  Indexed articles:  \\textit{Tiuryn, Jerzy; Rudnicki, Ryszard; W\u00f3jtowicz, Damian}, A case study of genome evolution: From continuous to discrete time model, 1-24 [Zbl 1097.92036]  \\textit{Halld\u00f3rsson, Magn\u00fas M.; Kortsarz, Guy}, Multicoloring: Problems and techniques, 25-41 [Zbl 1096.68684]  \\textit{Downey, Rod}, Some recent progress in algorithmic randomness, 42-83 [Zbl 1096.03055]  \\textit{Niedermeier, Rolf}, Ubiquitous parameterization -- invitation to fixed-parameter algorithms, 84-103 [Zbl 1096.68068]  \\textit{Vishkin, Uzi}, PRAM-On-Chip: A quest for not-so-obvious non-obviousness, 104-105 [Zbl 1096.68580]  \\textit{Brand, Matthew; Frisken, Sarah; Lesh, Neal; Marks, Joe; Nikovski, Daniel; Perry, Ron; Yedidia, Jonathan}, Theory and applied computing: Observations and anecdotes, 106-118 [Zbl 1097.68665]  \\textit{Bonelli, Eduardo; Compagnoni, Adriana; Dezani-Ciancaglini, Mariangiola; Garralda, Pablo}, Boxed ambients with communication interfaces, 119-148 [Zbl 1097.68083]  \\textit{Weil, Pascal}, Algebraic recognizability of languages, 149-175 [Zbl 1097.68078]  \\textit{Welzl, Emo}, Geometric optimization and unique sink orientations of cubes, 176-176 [Zbl 1097.90569]  \\textit{Koutsoupias, Elias}, Congestion games and coordination mechanisms, 177-179 [Zbl 1096.68517]  \\textit{Bodlaender, Hans L.; Fomin, Fedor V.}, Equitable colorings of bounded treewidth graphs, 180-190 [Zbl 1096.68116]  \\textit{Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M.}, The bidimensional theory of bounded-genus graphs, 191-203 [Zbl 1100.05095]  \\textit{Broersma, Hajo; Fomin, Fedor V.; Woeginger, Gerhard J.}, Parallel knock-out schemes in networks, 204-214 [Zbl 1096.68118]  \\textit{Caragiannis, Ioannis; Fishkin, Aleksei; Kaklamanis, Christos; Papaioannou, Evi}, Online algorithms for disk graphs, 215-226 [Zbl 1096.68119]  \\textit{B\u00f6ckenhauer, Hans-Joachim; Bongartz, Dirk}, Protein folding in the HP model on grid lattices with diagonals (extended abstract), 227-238 [Zbl 1097.92507]  \\textit{Chen, Hubie; P\u00e1l, Martin}, Optimization, games, and quantified constraint satisfaction, 239-250 [Zbl 1096.90028]  \\textit{Gronemeier, Andre}, Approximating Boolean functions by OBDDs, 251-262 [Zbl 1096.68032]  \\textit{Chleb\u00edk, Miroslav; Chleb\u00edkov\u00e1, Janka}, On approximation hardness of the minimum 2SAT-DELETION problem, 263-273 [Zbl 1096.68061]  \\textit{Kr\u00e1l', Daniel; Nejedl\u00fd, Pavel}, Group coloring and list group coloring are \\(\\Pi_{2}^{\\text{P}}\\)-complete (extended abstract), 274-286 [Zbl 1096.68627]  \\textit{Hemaspaandra, Edith; Hemaspaandra, Lane A.; Radziszowski, Stanis\u0142aw; Tripathi, Rahul}, Complexity results in graph reconstruction, 287-297 [Zbl 1096.68121]  \\textit{Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Khachiyan, Leonid; Makino, Kazuhisa}, Generating paths and cuts in multi-pole (di)graphs, 298-309 [Zbl 1096.68117]  \\textit{Nutov, Zeev; Yuster, Raphael}, Packing directed cycles efficiently, 310-321 [Zbl 1096.68123]  \\textit{Travers, Stephen D.}, The complexity of membership problems for circuits over sets of integers, 322-333 [Zbl 1096.68065]  \\textit{Hansen, Kristoffer Arnsfelt; Miltersen, Peter Bro}, Some meet-in-the-middle circuit lower bounds, 334-345 [Zbl 1096.68062]  \\textit{Beygelzimer, Alina; Ogihara, Mitsunori}, The enumerability of P collapses P to NC, 346-355 [Zbl 1096.68059]  \\textit{De Santis, Alfredo; Di Crescenzo, Giovanni; Persiano, Giuseppe}, On NC\\(^{1}\\) Boolean circuit composition of non-interactive perfect zero-knowledge, 356-367 [Zbl 1096.68060]  \\textit{Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald}, All superlinear inverse schemes are coNP-hard, 368-379 [Zbl 1096.68064]  \\textit{Nordh, Gustav}, The complexity of equivalence and isomorphism of systems of equations over finite groups, 380-391 [Zbl 1096.68069]  \\textit{B\u00f6hler, Elmar; Gla\u00dfer, Christian; Schwarz, Bernhard; Wagner, Klaus}, Generation problems, 392-403 [Zbl 1096.68067]  \\textit{Bab, Sebastian; Nickelsen, Arfst}, One query reducibilities between partial information classes, 404-415 [Zbl 1096.68058]  \\textit{Bernardi, Vincent; Durand, Bruno; Formenti, Enrico; Kari, Jarkko}, A new dimension sensitive property for cellular automata, 416-426 [Zbl 1096.68098]  \\textit{Theyssier, Guillaume}, Captive cellular automata, 427-438 [Zbl 1096.68100]  \\textit{Poupet, Victor}, Simulating 3D cellular automata with 2D cellular automata, 439-450 [Zbl 1096.68099]  \\textit{Fraigniaud, Pierre; Ilcinkas, David; Peer, Guy; Pelc, Andrzej; Peleg, David}, Graph exploration by a finite automaton, 451-462 [Zbl 1096.68080]  \\textit{Lee, Troy; Romashchenko, Andrei}, On polynomially time bounded symmetry of information, 463-475 [Zbl 1096.68074]  \\textit{Hitchcock, John M.; L\u00f3pez-Vald\u00e9s, Mar\u00eda; Mayordomo, Elvira}, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, 476-487 [Zbl 1096.68073]  \\textit{Fernau, Henning; Juedes, David}, A geometric approach to parameterized algorithms for domination problems on planar graphs, 488-499 [Zbl 1096.68167]  \\textit{Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge}, Polynomial time approximation schemes and parameterized complexity, 500-512 [Zbl 1096.68166]  \\textit{Loyer, Yann; Straccia, Umberto}, Epistemic foundation of the well-founded semantics over bilattices, 513-524 [Zbl 1096.68016]  \\textit{Lanotte, Ruggero; Maggiolo-Schettini, Andrea; Peron, Adriano}, Structural model checking for communicating hierarchical machines, 525-536 [Zbl 1096.68092]  \\textit{Ly, Olivier}, Compositional verification: Decidability issues using graph substitutions, 537-549 [Zbl 1096.68093]  \\textit{van Glabbeek, Rob; Plotkin, Gordon}, Event structures for resolvable conflict, 550-561 [Zbl 1096.68114]  \\textit{Epstein, Leah; Tassa, Tamir}, Optimal preemptive scheduling for general target functions, 562-573 [Zbl 1096.90015]  \\textit{Gairing, Martin; L\u00fccking, Thomas; Mavronicolas, Marios; Monien, Burkhard}, The price of anarchy for polynomial social cost, 574-585 [Zbl 1096.68010]  \\textit{Els\u00e4sser, Robert; Lorenz, Ulf; Sauerwald, Thomas}, Agent-based information handling in large networks, 586-598 [Zbl 1096.68009]  \\textit{Baumann, Nadine; K\u00f6hler, Ekkehard}, Approximating earliest arrival flows with flow-dependent transit times, 599-610 [Zbl 1096.90003]  \\textit{B\u00e9al, Marie-Pierre; Fiorenzi, Francesca; Perrin, Dominique}, A hierarchy of irreducible sofic shifts, 611-622 [Zbl 1096.68078]  \\textit{Lisitsa, Alexei; Potapov, Igor}, Membership and reachability problems for row-monomial transformations, 623-634 [Zbl 1096.68108]  \\textit{Pol\u00e1k, Libor}, On pseudovarieties of semiring homomorphisms, 635-647 [Zbl 1096.68097]  \\textit{\u00c9sik, Zolt\u00e1n; Kuich, Werner}, An algebraic generalization of \\(\\omega\\)-regular languages, 648-659 [Zbl 1096.68096]  \\textit{Crasmaru, Marcel; Gla\u00dfer, Christian; Regan, Kenneth W.; Sengupta, Samik}, A protocol for serializing unique strategies, 660-672 [Zbl 1097.68046]  \\textit{Bj\u00f6rklund, Henrik; Sandberg, Sven; Vorobyov, Sergei}, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, 673-685 [Zbl 1097.91020]  \\textit{Gimbert, Hugo; Zielonka, Wies\u0142aw}, When can you play positionally?, 686-697 [Zbl 1097.91022]  \\textit{Okhotin, Alexander}, The dual of concatenation, 698-710 [Zbl 1097.68068]  \\textit{Ambos-Spies, Klaus; Busse, Edgar}, Computational aspects of disjunctive sequences, 711-722 [Zbl 1097.03033]  \\textit{Domaratzki, Michael; Salomaa, Kai}, Decidability of trajectory-based equations, 723-734 [Zbl 1097.68057]  \\textit{Biedl, Therese; Hasan, Masud; L\u00f3pez-Ortiz, Alejandro}, Efficient view point selection for silhouettes of convex polyhedra, 735-747 [Zbl 1097.68130]  \\textit{Biedl, Therese; Lubiw, Anna; Spriggs, Michael J.}, Angles and lengths in reconfigurations of polygons and polyhedra, 748-759 [Zbl 1097.68132]  \\textit{Doerr, Benjamin; Hebbinghaus, Nils; Werth, S\u00f6ren}, Improved bounds and schemes for the declustering problem, 760-771 [Zbl 1097.68037]  \\textit{Hlin\u011bn\u00fd, Petr}, Crossing number is hard for cubic graphs, 772-782 [Zbl 1097.68047]  \\textit{Selivanov, Victor L.; Wagner, Klaus W.}, A reducibility for the dot-depth hierarchy, 783-793 [Zbl 1097.03035]  \\textit{Wich, Klaus}, Sublogarithmic ambiguity, 794-806 [Zbl 1097.68069]  \\textit{Petre, Elena}, An elementary proof for the non-parametrizability of the equation \\(xyz=zvx\\), 807-817 [Zbl 1097.68112]  \\textit{Ilie, Lucian; Ochem, Pascal; Shallit, Jeffrey}, A generalization of repetition threshold, 818-826 [Zbl 1097.68110]  \\textit{Nishimura, Harumichi; Yamakami, Tomoyuki}, An algorithmic argument for nonadaptive query complexity lower bounds on advised quantum computation (extended abstract), 827-838 [Zbl 1097.68567]  \\textit{Kawachi, Akinori; Kobayashi, Hirotada; Koshiba, Takeshi; Putra, Raymond H.}, Universal test for quantum one-way permutations, 839-850 [Zbl 1097.68038]  \\textit{Beaudry, Martin; Fernandez, Jos\u00e9 M.; Holzer, Markus}, A common algebraic description for probabilistic and quantum computations (extended abstract), 851-862 [Zbl 1097.68566]  \\textit{Andr\u00e9, Yves; Caron, Anne-C\u00e9cile; Debarbieux, Denis; Roos, Yves; Tison, Sophie}, Extraction and implication of path constraints, 863-875 [Zbl 1097.68028]  \\textit{Bouchou, B\u00e9atrice; Duarte, Denio; Halfeld Ferrari Alves, M\u00edrian; Laurent, Dominique; Musicante, Martin A.}, Schema evolution for XML: A consistency-preserving approach, 876-888 [Zbl 1097.68550]  \\textit{Martens, Wim; Neven, Frank; Schwentick, Thomas}, Complexity of decision problems for simple regular expressions, 889-900 [Zbl 1097.68066]","type":"string"},"datatype":"string"},"type":"statement","id":"Q1769767$A4CC1977-CC8E-41CC-89E2-859A6D7FCE28","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed293b811733fa9438a72e1b6ba5680a0d2aac9e","datavalue":{"value":"68-06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1769767$D6F46FCD-1B5D-48DC-AAFF-83CB5E3F0269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1769767$EB7BF383-49C7-475D-B0A1-0B87A7C8D1D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f2c17db95e93f9a5a19ff6c68b3a1df8b0c021e","datavalue":{"value":"00B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1769767$D4187FE4-20C6-4F40-ABB5-B1DFAACA0818","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"79800b2f6be1203e068aa44350e0682f5f56e100","datavalue":{"value":"2148966","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1769767$8BD085F9-216B-4117-8405-00C222FA78A6","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1769767$FCCBEA81-AC2B-4CEF-9EDE-C1884FE6CF46","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"34f7a0615602149851a7f9206520b7271140d8c0","datavalue":{"value":"https://doi.org/10.1007/b99679","type":"string"},"datatype":"url"},"type":"statement","id":"Q1769767$065523C9-217A-4478-A5A0-9EFF7FBC3D3A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a859c61ea0984951da05548e5c59ff8d6a2f01e3","datavalue":{"value":"W2488008928","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1769767$63C828C1-368D-44E5-9BDC-209B8B868704","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b74d4b224f9781b2c9d6ff0aa730f6de2bd89c8a","datavalue":{"value":"10.1007/B99679","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1769767$7FD0892B-FD28-4C9B-8958-38DD4C57B265","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1769767","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1769767"}}}}}