{"entities":{"Q5943787":{"pageid":8120589,"ns":120,"title":"Item:Q5943787","lastrevid":102022508,"modified":"2026-06-06T03:19:47Z","type":"item","id":"Q5943787","labels":{"en":{"language":"en","value":"Fundamentals of computation theory. 13th international symposium, FCT 2001, Riga, Latvia, August 22--24, 2001. Proceedings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1648474"}},"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":"Q5943787$ED6C2B7C-C583-42E9-B081-D20262E9DD1E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a4603ef80e0cac0fd091426812a0ed82d8acccb8","datavalue":{"value":{"text":"Fundamentals of computation theory. 13th international symposium, FCT 2001, Riga, Latvia, August 22--24, 2001. Proceedings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5943787$C41632B0-A8F2-4EC7-BCEA-61922024062D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e489c313538c2d9f189b62c4c1ec5a55bc0b4ed","datavalue":{"value":"0969.00084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943787$62E4E420-E92B-4255-9AE1-9761A9A2C3E6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1ea207e32aea713ec389d0458f13c1f4439ab294","datavalue":{"value":"10.1007/3-540-44669-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943787$6B7BF451-339C-4ABC-AEFA-B4E5781157D7","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":"Q5943787$BAF8564F-89F9-4AC3-AA99-C05DDE4F6E2C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"175f29debcecd1c84977f0ceae8e3095d272950b","datavalue":{"value":{"time":"+2001-09-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5943787$1020AB72-D56A-425A-889E-4CE8DD1EE70F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2bba320573229a3fc788cec273102398ec956fd7","datavalue":{"value":"The articles of mathematical interest will be reviewed individually. The preceding symposium (12th, 1999) has been reviewed (see Zbl 0921.00033).  Indexed articles:  \\textit{B\u0101rzdi\u0146\u0161, J\u0101nis; Freivalds, R\u016bsi\u0146\u0161; Smith, Carl H.}, Towards axiomatic basis of inductive inference, 1-13 [Zbl 1004.68078]  \\textit{Jansen, Klaus}, Approximation algorithms for fractional covering and packing problems, and applications, 14 [Zbl 0999.68547]  \\textit{Karhum\u00e4ki, Juhani}, Challenges of commutation. An advertisement, 15-23 [Zbl 0999.68517]  \\textit{Karpinski, Marek}, Approximating bounded degree instances of NP-hard problems, 24-34 [Zbl 1003.90055]  \\textit{Plotkin, Boris; Plotkin, Tanya}, Universal algebra and computer science, 35-44 [Zbl 0999.08005]  \\textit{Vazirani, Umesh}, Quantum algorithms, 45-46 [Zbl 0999.68546]  \\textit{Ablayev, Farid; Ablayeva, Svetlana}, A discrete approximation and communication complexity approach to the superposition problem, 47-58 [Zbl 1005.68081]  \\textit{Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek}, On computational power of quantum branching programs, 59-70 [Zbl 0999.68071]  \\textit{Baier, Harald}, Efficient computation of singular moduli with application in cryptography, 71-82 [Zbl 1001.11057]  \\textit{B\u0113rzi\u0146a, Aija; Bonner, Richard}, Ambainis-Freivalds' algorithm for measure-once automata, 83-93 [Zbl 0999.68510]  \\textit{C\u012brulis, J\u0101nis}, Are there essentially incomplete knowledge representation systems?, 94-105 [Zbl 0999.68211]  \\textit{Ciura, Marcin}, Best increments for the average case of Shellsort, 106-117 [Zbl 0999.68543]  \\textit{Fomin, Fedor V.; Kratsch, Dieter; Novelli, Jean-Christophe}, Approximating minimum cocolourings, 118-125 [Zbl 1001.05054]  \\textit{Freivalds, K\u0101rlis}, Curved edge routing, 126-137 [Zbl 0999.68544]  \\textit{Gasieniec, Leszek; Potapov, Igor}, Time/space efficient compressed pattern matching, 138-149 [Zbl 0999.68538]  \\textit{Heinemann, Bernhard}, Modelling change with the aid of knowledge and time, 150-161 [Zbl 0999.68212]  \\textit{Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, J\u00f6rg}, If \\(\\text{P} \\neq \\text{NP}\\) then some strongly noninvertible functions are invertible, 162-171 [Zbl 0999.68076]  \\textit{Hirata, Kouichi; Sakamoto, Hiroshi}, Prediction-preserving reducibility with membership queries on formal languages, 172-183 [Zbl 0999.68520]  \\textit{J\u00e4rvinen, Jouni}, Dense families and key functions of database relation instances, 184-192 [Zbl 0999.68508]  \\textit{Karhum\u00e4ki, Juhani; Plandowski, Wojciech; Rytter, Wojciech}, On the complexity of decidable cases of commutation problem for languages (extended abstract), 193-203 [Zbl 0999.68522]  \\textit{Kuich, Werner}, Cones, semi-AFPs, and AFPs of algebraic power series, 204-216 [Zbl 0999.68128]  \\textit{Kudlek, Manfred; Rogozhin, Yurii}, New small universal circular Post machines, 217-226 [Zbl 0999.68070]  \\textit{Kuske, Dietrich}, Divisibility monoids: Presentation, word problem, and rational languages, 227-239 [Zbl 0999.68129]  \\textit{Lanotte, Ruggero; Maggiolo-Schettini, Andrea; Tini, Simone}, Concurrency in timed automata, 240-251 [Zbl 0999.68135]  \\textit{Lafitte, Gr\u00e9gory}, How powerful are infinite time machines?, 252-263 [Zbl 0999.68069]  \\textit{Linde, \u0122irts}, Equivalence problem of composite class diagrams, 264-274 [Zbl 0999.68541]  \\textit{Monnot, J\u00e9r\u00f4me; Paschos, Vangelis Th.; Toulouse, Sophie}, Differential approximation results for the traveling salesman problem with distances 1 and 2 (extended abstract), 275-286 [Zbl 1003.90035]  \\textit{Moskaljova, Nataly S.; Virbitskaite, Irina B.}, On the category of event structures with dense time, 287-298 [Zbl 0999.68136]  \\textit{Nickelsen, Arfst; Tandau, Till}, Closure of polynomial time partial information classes under polynomial time reduction, 299-310 [Zbl 1005.68074]  \\textit{Rettinger, Robert; Verbeek, Rutger}, Monte-Carlo polynomial versus linear time -- the truth-table case, 311-322 [Zbl 0999.68077]  \\textit{Selivanov, V. L.}, Relating automata-theoretic hierarchies to complexity-theoretic hierarchies, 323-334 [Zbl 0999.68078]  \\textit{Shoudai, Takayoshi; Uchida, Tomoyuki; Miyahara, Tetsuhiro}, Polynomial time algorithms for finding unordered tree patterns with internal variables, 335-346 [Zbl 0999.68111]  \\textit{Trahtman, A. N.}, Piecewise and local threshold testability of DFA, 347-358 [Zbl 0999.68519]  \\textit{Walicki, Micha\u0142; Hodzic, Adis; Meldal, Sigurd}, Compositional homomorphisms of relational structures (modeled as multialgebras), 359-371 [Zbl 0999.08004]  \\textit{Buls, J\u0101nis; Bu\u017ea, Vaira; Glaudi\u0161, Roberts}, Representation of autonomous automata, 372-375 [Zbl 0999.68521]  \\textit{Ciamarra, Massimo Pica}, Quantum reversibility and a new model of quantum automaton, 376-379 [Zbl 0999.68512]  \\textit{Dubrovsky, Andrej}, Space-efficient 1. 5-way quantum Turing machine, 380-383 [Zbl 0999.68513]  \\textit{Gambin, Anna; Pokarowski, Piotr}, A combinatorial aggregation algorithm for stationary distribution of a large Markov chain. (Extended abstract), 384-387 [Zbl 1008.60508]  \\textit{Kiltz, Eike}, A primitive for proving the security of every bit and about universal hash functions \\& hard core bits, 388-391 [Zbl 0999.94520]  \\textit{Lipyanski, Ruvim}, Pythagorean triples in unification theory of nilpotent rings, 392-395 [Zbl 1007.16013]  \\textit{Ollinger, Nicolas}, Two-states bilinear intrinsically universal cellular automata, 396-399 [Zbl 0999.68526]  \\textit{Papazian, Christophe; R\u00e9mila, Eric}, Linear time recognizer for subsets of \\({\\mathbb Z}^2\\), 400-403 [Zbl 0999.68518]  \\textit{Plotkin, Tanya}, Fuzzy sets and algorithms of distributed task allocation for cooperative agents, 404-407 [Zbl 0999.68540]  \\textit{Rozenblat, Bella V.}, On recursively enumerable subsets of \\(\\mathbb{N}\\) and Rees matrix semigroups over \\((\\mathbb{Z}_3;+)\\), 408-411 [Zbl 1005.03041]  \\textit{Scegulnaja, Oksana}, Quantum real-time Turing machine, 412-415 [Zbl 1005.68067]  \\textit{Sokolov, Andrew V.}, Mathematical models and optimal algorithms of dynamic data structure control, 416-419 [Zbl 0999.68507]  \\textit{Sokratova, Olga}, Linear automata and recognizable subsets in free semirings, 420-423 [Zbl 0999.68525]  \\textit{Tombak, Mati; Isotamm, Ain; Tamme, T\u00f5nu}, On logical method for counting Dedekind numbers, 424-427 [Zbl 0999.03504]  \\textit{Valiente, Gabriel}, A general method for graph isomorphism, 428-431 [Zbl 1001.05085]  \\textit{Afrati, F.; Milis, I.}, Designing PTASs for MIN-SUM scheduling problems (short version), 432-444 [Zbl 0999.68501]  \\textit{Brandst\u00e4dt, Andreas}, On robust algorithms for the maximum weight stable set problem, 445-458 [Zbl 1001.05111]  \\textit{Doerr, Benjamin}, Structured randomized rounding and coloring (extended abstract), 461-471 [Zbl 0999.68535]  \\textit{Epstein, Leah; van Stee, Rob}, Optimal online flow time with resource augmentation, 472-482 [Zbl 0999.68023]  \\textit{Erlebach, Thomas; Vukadinovi\u0107, Danica}, New results for path problems in generalized stars, complete graphs, and brick wall graphs, 483-494 [Zbl 0999.68160]  \\textit{Fishkin, Aleksei V.; Jansen, Klaus; Porkolab, Lorant}, On minimizing average weighted completion time: A PTAS for scheduling general multiprocessor tasks, 495-507 [Zbl 0999.68024]  \\textit{Fomin, Fedor V.; Lingas, Andrzej}, Approximation algorithms for time-dependent orienteering, 508-515 [Zbl 1003.90046]  \\textit{Kr\u00e1l', Daniel}, On complexity of colouring mixed hypertrees, 516-524 [Zbl 1001.05110]  \\textit{Mastrolilli, Monaldo}, Combining arithmetic and geometric rounding techniques for knapsack problems, 525-534 [Zbl 1003.90034]  \\textit{Mielik\u00e4inen, Taneli; Ukkonen, Esko}, The complexity of maximum matroid-greedoid intersection, 535-539 [Zbl 0999.68534]","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943787$88037C1F-E006-4385-8D54-554AFE38F22F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f2c17db95e93f9a5a19ff6c68b3a1df8b0c021e","datavalue":{"value":"00B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943787$3FC84B0E-7E18-44BE-9D9C-1B1EBC38BC73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed293b811733fa9438a72e1b6ba5680a0d2aac9e","datavalue":{"value":"68-06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943787$723A8D35-6FD1-4AB4-9055-0E90A1854F9E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"43bc534007df0e957de9cb7823891e200a9aa334","datavalue":{"value":"1648474","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943787$F2A5C61F-05DE-4E0E-9FB3-21AB92451D34","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd65c0ac03a918342070836d803a1dbabde9d5f3","datavalue":{"value":"Riga (Latvia)","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943787$0DE459E4-3DB3-4539-A0E3-81BF5014C375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c4c4bb5a86a0fdf66f908b603f2f6975f5ef6fc","datavalue":{"value":"Proceedings","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943787$EF299637-CE2E-4B9C-A996-7C9E7FBDEFE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b165f2c80f889e3c73f8a20cfd816794dd15c80","datavalue":{"value":"Symposium","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943787$AEF9E728-1FD1-4EA5-BB08-A6CC1C6293E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40b7fb579486932522e675a998d00ac01919fa54","datavalue":{"value":"FCT 2001","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943787$1C4F7815-2BE5-4B96-B4F6-8F657A9D1C5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"716241f0bdfeff767a37ed2bdd3b6b87a9e81f3f","datavalue":{"value":"Computation theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943787$3760D11B-0822-4128-9B5A-C746F63C73FC","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":"Q5943787$C3379A14-540A-47F3-909D-A5D0912A53D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"72d622687dac55395e8f1ea6c7fb7c2954f56975","datavalue":{"value":"https://doi.org/10.1007/3-540-44669-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q5943787$A86B4988-0A74-45EC-A1B8-169ABE58C48B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac4a7caa6dc36fd00b502adeb2c8ac007bb0ccff","datavalue":{"value":"W4206072013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943787$C0CA5368-94E3-4A28-B47D-D23A21AFFE79","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fundamentals of computation theory. 13th international symposium, FCT 2001, Riga, Latvia, August 22--24, 2001. Proceedings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fundamentals_of_computation_theory._13th_international_symposium,_FCT_2001,_Riga,_Latvia,_August_22--24,_2001._Proceedings"}}}}}