×

zbMATH — the first resource for mathematics

Mathematical foundations of computer science 2013. 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26–30, 2013. Proceedings. (English) Zbl 1270.68020
Lecture Notes in Computer Science 8087. Berlin: Springer (ISBN 978-3-642-40312-5/pbk). xvi, 851 p. (2013).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding symposium see [Zbl 1246.68054].
Indexed articles:
Buss, Sam, Alternation trading proofs and their limitations, 1-7 [Zbl 1400.68083]
Epstein, Leah, Bin packing games with selfish items, 8-21 [Zbl 1400.91007]
Goubault-Larrecq, Jean, A constructive proof of the topological Kruskal theorem, 22-41 [Zbl 1403.03126]
Angel, Eric; Bampis, Evripidis; Kononov, Alexander; Paparas, Dimitris; Pountourakis, Emmanouil; Zissimopoulos, Vassilis, Clustering on \(k\)-edge-colored graphs, 50-61 [Zbl 1398.68384]
Antoniadis, Antonios; Huang, Chien-Chung; Ott, Sebastian; Verschae, José, How to pack your items when you have to buy your knapsack, 62-73 [Zbl 1400.90253]
Bacci, Giorgio; Bacci, Giovanni; Larsen, Kim G.; Mardare, Radu, Computing behavioral distances, compositionally, 74-85 [Zbl 1400.68144]
Bala, Sebastian, Which finitely ambiguous automata recognize finitely sequential functions? (extended abstract), 86-97 [Zbl 1398.68295]
Bárány, Vince; Benedikt, Michael; ten Cate, Balder, Rewriting guarded negation queries, 98-110 [Zbl 1398.68120]
Beckmann, Arnold; Pudlák, Pavel; Thapen, Neil, Parity games and propositional proofs, 111-122 [Zbl 1343.03043]
Bedon, Nicolas, Logic and branching automata, 123-134 [Zbl 1398.68297]
Bender, Marco; Thielen, Clemens; Westphal, Stephan, A constant factor approximation for the generalized assignment problem with minimum quantities and unit size items, 135-145 [Zbl 1400.90255]
Benedikt, Michael; Engelfriet, Joost; Maneth, Sebastian, Determinacy and rewriting of top-down and MSO tree transformations, 146-158 [Zbl 1398.68104]
Berkholz, Christoph; Verbitsky, Oleg, On the speed of constraint propagation and the time complexity of arc consistency testing, 159-170 [Zbl 1378.68058]
Björklund, Henrik; Martens, Wim; Schwentick, Thomas, Validity of tree pattern queries with respect to schema information, 171-182 [Zbl 1398.68187]
Bonatti, Piero A.; Faella, Marco; Galdi, Clemente; Sauro, Luigi, Auctions for partial heterogeneous preferences, 183-194 [Zbl 1400.91210]
Brandstädt, Andreas; Milanič, Martin; Nevries, Ragnar, New polynomial cases of the weighted efficient domination problem, 195-206 [Zbl 1398.68218]
Bringmann, Karl, Bringing order to special cases of Klee’s measure problem, 207-218 [Zbl 1400.68082]
Bringmann, Karl; Engels, Christian; Manthey, Bodo; Raghavendra Rao, B. V., Random shortest paths: non-Euclidean instances for metric optimization problems, 219-230 [Zbl 1319.90071]
Buckheister, P.; Zetzsche, Georg, Semilinearity and context-freeness of languages accepted by valence automata, 231-242 [Zbl 1398.68302]
Buhrman, Harry; Fortnow, Lance; Hitchcock, John M.; Loff, Bruno, Learning reductions to sparse sets, 243-253 [Zbl 1400.68074]
Chadha, Rohit; Sistla, A. Prasad; Viswanathan, Mahesh, Probabilistic automata with isolated cut-points, 254-265 [Zbl 1398.68304]
Chen, Taolue; Forejt, Vojtěch; Kwiatkowska, Marta; Simaitis, Aistis; Wiltsche, Clemens, On stochastic games with multiple objectives, 266-277 [Zbl 1400.91040]
Cohen, Sarel; Fiat, Amos; Hershcovitch, Moshik; Kaplan, Haim, Minimal indices for successor search (extended abstract), 278-289 [Zbl 1398.68105]
Creignou, Nadia; Meier, Arne; Müller, Julian-Steffen; Schmidt, Johannes; Vollmer, Heribert, Paradigms for parameterized enumeration, 290-301 [Zbl 1362.68103]
Czerwiński, Wojciech; Jančar, Petr; Kot, Martin; Sawa, Zdeněk, Complexity of checking bisimilarity between sequential and parallel processes, 302-313 [Zbl 1398.68361]
Durocher, Stephane; Mehrabi, Saeed, Guarding orthogonal art galleries using sliding cameras: algorithmic and hardness results, 314-324 [Zbl 1400.68247]
Durocher, Stephane; Shah, Rahul; Skala, Matthew; Thankachan, Sharma V., Linear-space data structures for range frequency queries on arrays and trees, 325-336 [Zbl 1400.68062]
Eggert, Sebastian; Schnoor, Henning; Wilke, Thomas, Noninterference with local policies, 337-348 [Zbl 1398.68363]
Elmasry, Amr; Katajainen, Jyrki, In-place binary counters, 349-360 [Zbl 1398.68106]
Epstein, Leah; Zebedat-Haider, Hanan, Rent or buy problems with a fixed time horizon, 361-372 [Zbl 1329.68298]
Felsner, Stefan; Mertzios, George B.; Musta, Irina, On the recognition of four-directional orthogonal ray graphs, 373-384 [Zbl 1398.68394]
Feng, Yuan; Yu, Nengkun; Ying, Mingsheng, Reachability analysis of recursive quantum Markov chains, 385-396 [Zbl 1400.68073]
Fink, Martin; Pupyrev, Sergey, Ordering metro lines by block crossings, 397-408 [Zbl 1398.68395]
Finkel, Alain; Göller, Stefan; Haase, Christoph, Reachability in register machines with polynomial updates, 409-420 [Zbl 1398.68160]
Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Janne H., On the parameterized complexity of cutting a few vertices from a graph, 421-432 [Zbl 1398.68231]
Fournier, Hervé; Perifel, Sylvain; de Verclos, Rémi, On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant, 433-444 [Zbl 1398.68192]
Froese, Vincent; van Bevern, René; Niedermeier, Rolf; Sorge, Manuel, A parameterized complexity analysis of combinatorial feature selection problems, 445-456 [Zbl 1333.68142]
Ganian, Robert; Slivovsky, Friedrich; Szeider, Stefan, Meta-kernelization with structural parameters, 457-468 [Zbl 1400.68089]
Goldberg, Andrew V.; Razenshteyn, Ilya; Savchenko, Ruslan, Separating hierarchical and general hub labelings, 469-479 [Zbl 1398.68397]
Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan, Solving 3-superstring in \(3^{n/3}\) time, 480-491 [Zbl 1398.68238]
Goyal, Prachi; Kamat, Vikram; Misra, Neeldhara, On the parameterized complexity of the maximum edge 2-coloring problem, 492-503 [Zbl 1398.68239]
Gurvits, Leonid, A note on deterministic poly-time algorithms for partition functions associated with Boolean matrices with prescribed row and column sums, 504-515 [Zbl 1398.68242]
Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V., Polynomial threshold functions and Boolean threshold circuits, 516-527 [Zbl 1312.68088]
Heußner, Alexander; Kartzow, Alexander, Reachability in higher-order-counters, 528-539 [Zbl 1400.68104]
Hitchcock, John M.; Pavan, A., Length-increasing reductions for PSPACE-completeness, 540-550 [Zbl 1398.68182]
Huang, Shenwei, Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs, 551-558 [Zbl 1400.68075]
Huschenbett, Martin; Liu, Jiamou, A polychromatic Ramsey theory for ordinals, 559-570 [Zbl 06210002]
I, Tomohiro; Matsubara, Wataru; Shimohira, Kouji; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki; Narisawa, Kazuyuki; Shinohara, Ayumi, Detecting regularities on grammar-compressed strings, 571-582 [Zbl 1398.68705]
Krebs, Andreas; Limaye, Nutan; Mahajan, Meena; Sreenivasaiah, Karteek, Small depth proof systems, 583-594 [Zbl 1400.68092]
Kunc, Michal; Okhotin, Alexander, Reversibility of computations in graph-walking automata, 595-606 [Zbl 1398.68317]
Kupferman, Orna; Mosheiff, Jonathan, Prime languages, 607-618 [Zbl 1398.68318]
Kuske, Dietrich, Logical aspects of the lexicographic order on 1-counter languages, 619-630 [Zbl 1400.68109]
Köbler, Johannes; Kuhnert, Sebastian; Verbitsky, Oleg, Helly circular-arc graph isomorphism is in logspace, 631-642 [Zbl 1388.68126]
Lazić, Ranko; Ouaknine, Joël; Worrell, James, Zeno, Hercules and the Hydra: downward rational termination is Ackermannian, 643-654 [Zbl 1400.03034]
Kozen, Dexter; Mardare, Radu; Panangaden, Prakash, Strong completeness for Markovian logics, 655-666 [Zbl 06210010]
Mengel, Stefan, Arithmetic branching programs with memory, 667-678 [Zbl 1398.68184]
Misra, Neeldhara; Panolan, Fahad; Saurabh, Saket, Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?, 679-690 [Zbl 1400.68160]
Muscholl, Anca; Schewe, Sven, Unlimited decidability of distributed synthesis with limited missing knowledge, 691-703 [Zbl 1398.68371]
Müller, Moritz; Szeider, Stefan, Revisiting space in proof complexity: treewidth and pathwidth, 704-716 [Zbl 1400.03073]
Pietracaprina, Andrea; Pucci, Geppino; Silvestri, Francesco; Vandin, Fabio, Space-efficient parallel algorithms for combinatorial search problems, 717-728 [Zbl 1398.68497]
Place, Thomas; van Rooijen, Lorijn; Zeitoun, Marc, Separating regular languages by piecewise testable and unambiguous languages, 729-740 [Zbl 1400.68113]
Rabinovich, Alexander, An unusual temporal logic, 741-752 [Zbl 1400.03035]
Ranzato, Francesco, A more efficient simulation algorithm on Kripke structures, 753-764 [Zbl 1400.68143]
Schmidt, Jens M., A planarity test via construction sequences, 765-776 [Zbl 1400.05064]
Fernández, Ariel Germán; Soltys, Michael, Feasible combinatorial matrix theory, 777-788 [Zbl 1400.03072]
Souza, Alexander, Approximation algorithms for generalized plant location, 789-800 [Zbl 1398.68684]
Takahashi, Yasuhiro; Yamazaki, Takeshi; Tanaka, Kazuyuki, Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates, 801-812 [Zbl 1400.68077]
Tavenas, Sébastien, Improved bounds for reduction to depth 4 and depth 3, 813-824 [Zbl 1360.68484]
Zehavi, Meirav, Parameterized algorithms for module motif, 825-836 [Zbl 1353.68140]
Zeume, Thomas; Schwentick, Thomas, On the quantifier-free dynamic complexity of reachability, 837-848 [Zbl 1371.68063]

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