×

zbMATH — the first resource for mathematics

SOFSEM 2012: Theory and practice of computer science. 38th conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 21–27, 2012. Proceedings. (English) Zbl 1236.68005
Lecture Notes in Computer Science 7147. Berlin: Springer (ISBN 978-3-642-27659-0/pbk). xvii, 674 p. (2012).

Show indexed articles as search result.

The articles of mathematical interest will be reviewed individually. For the preceding conference see [Zbl 1205.68007].
Indexed articles:
Cucker, Felipe, The legacy of Turing in numerical analysis, 1-13 [Zbl 1274.01074]
van Emde Boas, Peter, Turing machines for dummies. Why representations do matter, 14-30 [Zbl 1298.68092]
Gurevich, Yuri, What is an algorithm?, 31-42 [Zbl 1298.68091]
Wiedermann, Jiří, Towards computational models of artificial cognitive systems that can, in principle, pass the Turing test, 44-63 [Zbl 1298.68210]
Pietrzak, Krzysztof, Cryptography from learning parity with noise, 99-114 [Zbl 1298.94103]
Warwick, Kevin, Not another look at the Turing test!, 130-140 [Zbl 1298.68209]
Aceto, Luca; de Frutos-Escrig, David; Gregorio-Rodríguez, Carlos; Ingólfsdóttir, Anna, The equational theory of weak complete simulation semantics over BCCSP, 141-152 [Zbl 1298.68161]
Blin, Guillaume; Bonizzoni, Paola; Dondi, Riccardo; Rizzi, Romeo; Sikora, Florian, Complexity insights of the minimum duplication problem, 153-164 [Zbl 1298.68108]
Çapuni, Ilir; Gács, Peter, A Turing machine resisting isolated bursts of faults, 165-176 [Zbl 1298.68089]
Čepek, Ondřej; Kučera, Petr; Vlček, Václav, Properties of SLUR formulae, 177-189 [Zbl 1298.68110]
Cheilaris, Panagiotis; Keszegh, Balázs; Pálvölgyi, Dömötör, Unique-maximum and conflict-free coloring for hypergraphs and tree graphs, 190-201 [Zbl 1298.05108]
Couturier, Jean-François; Heggernes, Pinar; van’t Hof, Pim; Kratsch, Dieter, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, 202-213 [Zbl 1298.05246]
Damaschke, Peter; Muhammad, Azam Sheikh, Randomized group testing both query-optimal and minimal adaptive, 214-225 [Zbl 1298.68052]
Ebbing, Johannes; Lohmann, Peter, Complexity of model checking for modal dependence logic, 226-237 [Zbl 1298.68170]
Eğecioğlu, Ömer; Ibarra, Oscar H.; Tran, Nicholas Q., Multitape NFA: weak synchronization of the input heads, 238-250 [Zbl 1298.68131]
Filiot, Emmanuel; Servais, Frédéric, Visibly pushdown transducers with look-ahead, 251-263 [Zbl 1298.68133]
Gál, Anna; Jang, Jing-Tang, A generalization of Spira’s theorem and circuits with small segregators or separators, 264-276 [Zbl 1298.68090]
Gazda, Maciej W.; Willemse, Tim A. C., Consistent consequence for Boolean equation systems, 277-288 [Zbl 1298.68173]
Golovach, Petr A.; Paulusma, Daniël; Song, Jian, 4-coloring \(H\)-free graphs when \(H\) is small, 289-300 [Zbl 1298.05117]
Goto, Keisuke; Bannai, Hideo; Inenaga, Shunsuke; Takeda, Masayuki, Computing \(q\)-gram non-overlapping frequencies on SLP compressed texts, 301-312 [Zbl 1302.68338]
Jansen, Klaus, A fast approximation scheme for the multiple knapsack problem, 313-324 [Zbl 1302.90183]
Junosza-Szaniawski, Konstanty; Tuczyński, Michał, Counting maximal independent sets in subcubic graphs, 325-336 [Zbl 1302.05192]
Kari, Lila; Kopecki, Steffen; Seki, Shinnosuke, Iterated hairpin completions of non-crossing words, 337-348 [Zbl 1302.68167]
Krug, Sacha, On the approximation ratio of the path matching Christofides algorithm, 349-360 [Zbl 1302.90185]
Lavado, Giovanna J.; Pighizzini, Giovanni, Parikh’s theorem and descriptional complexity, 361-372 [Zbl 1302.68170]
Lingas, Andrzej; Sledneu, Dzmitry, A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs, 373-384 [Zbl 1302.05194]
Neary, Turlough; Woods, Damien, The complexity of small universal Turing machines: a survey, 385-405 [Zbl 1302.68117]
Šíma, Jiří; Žák, Stanislav, A sufficient condition for sets hitting the class of read-once branching programs of width 3 (extended abstract), 406-418 [Zbl 1302.68118]
Yan, Jun, Complete problem for perfect zero-knowledge quantum proof, 419-430 [Zbl 1302.81086]
Zhang, Chenyi; Pang, Jun, An algorithm for probabilistic alternating simulation, 431-442 [Zbl 1302.68205]
Beneš, Nikola; Černá, Ivana; Štefaňák, Filip, Factorization for component-interaction automata, 554-565 [Zbl 1302.68149]
Kutyłowski, Mirosław; Gȩbala, Maciej, Optimizing segment based document protection, 566-575 [Zbl 1302.68113]
Pettai, Martin; Laud, Peeter, Securing the future – an information flow analysis of a distributed OO language, 576-587 [Zbl 1302.68051]
Bordeaux, Lucas; Marques-Silva, Joao, Knowledge compilation with empowerment, 612-624 [Zbl 1302.68248]
Iša, Jiří; Reitermanová, Zuzana; Sýkora, Ondřej, Cost-sensitive classification with unconstrained influence diagrams, 625-636 [Zbl 1302.68233]

MSC:
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Qxx Theory of computing
00B25 Proceedings of conferences of miscellaneous specific interest
PDF BibTeX XML Cite
Full Text: DOI