Theory of Computing Systems, Volume 46

Volume 46, Number 1, January 2010

• Sergei N. Artëmov, Volker Diekert, Dima Grigoriev:
  Preface. 1
  
• Alexander Rybalov:
  Generic Complexity of Presburger Arithmetic. 2-8
  
• Meena Mahajan, Jayalal M. N. Sarma:
  On the Complexity of Matrix Rank and Rigidity. 9-26
  
• Artur Jez, Alexander Okhotin:
  Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth. 27-58
  
• Maxim A. Babenko:
  A Fast Algorithm for the Path 2-Packing Problem. 59-79
  
• Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen D. Travers, Matthias Waldherr:
  Equivalence Problems for Circuits over Sets of Natural Numbers. 80-103
  
• Benjamin Hoffmann, Mikhail Lifshits, Yury Lifshits, Dirk Nowotka:
  Maximal Intersection Queries in Randomized Input Models. 104-119
  
• Qi Cheng, Sergey P. Tarasov, Mikhail N. Vyalyi:
  Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing. 120-142
  
• Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
  Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? 143-156
  

Volume 46, Number 2, February 2010

• Tetsuo Asano, Peter Brass, Shinji Sasahara:
  Disc Covering Problem with Application to Digital Halftoning. 157-173
  
• Florin Manea, Maurice Margenstern, Victor Mitrana, Mario J. Pérez-Jiménez:
  A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors. 174-192
  
• Rahul Tripathi:
  The 1-Versus-2 Queries Problem Revisited. 193-221
  
• Piotr Faliszewski, Mitsunori Ogihara:
  On the Autoreducibility of Functions. 222-245
  
• Leah Epstein, Csanád Imreh, Asaf Levin:
  Class Constrained Bin Covering. 246-260
  
• Peter Damaschke:
  Fixed-Parameter Enumerability of Cluster Editing and Related Problems. 261-283
  
• Saverio Caminiti, Emanuele G. Fusco, Rossella Petreschi:
  Bijective Linear Time Coding and Decoding for k-Trees. 284-300
  
• Stasys Jukna:
  Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits. 301-310
  
• Michael R. Fellows, Jörg Flum, Danny Hermelin, Moritz Müller, Frances A. Rosamond:
  W-Hierarchies Defined by Symmetric Gates. 311-339
  
• Valentin V. Andreev, Timothy H. McNicholl:
  Computing Interpolating Sequences. 340-350
  
• Christian Choffrut, Flavio D'Alessandro, Stefano Varricchio:
  On Bounded Rational Trace Languages. 351-369
  
• Peter Jonsson, Gustav Nordh:
  Approximability of Clausal Constraints. 370-395
  

Volume 46, Number 3, April 2010

• Wolfgang Thomas, Pascal Weil:
  Preface of STACS 2007 Special Issue. 397
  
• Jin-yi Cai, Pinyan Lu:
  On Symmetric Signatures in Holographic Algorithms. 398-415
  
• Artur Czumaj, Christian Sohler:
  Small Space Representations for Metric Min-sum k-Clustering and Their Applications. 416-442
  
• Jean Berstel, Luc Boasson, Olivier Carton, Isabelle Fagnot:
  Sturmian Trees. 443-478
  
• Enrico Formenti, Petr Kurka, Ondrej Zahradník:
  A Search Algorithm for Subshift Attractors of Cellular Automata. 479-498
  
• Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao:
  Arithmetizing Classes Around NC\textsf{NC}¹ and L\textsf{L}. 499-522
  
• Amin Coja-Oghlan, Michael Krivelevich, Dan Vilenchik:
  Why Almost All k-Colorable Graphs Are Easy to Color. 523-565
  
• Hans L. Bodlaender, Thomas C. van Dijk:
  A Cubic Kernel for Feedback Vertex Set and Loop Cutset. 566-597
  
• Laurent Bienvenu:
  Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity. 598-617
  

Volume 46, Number 4, May 2010

• Sergei N. Artëmov, Volker Diekert, Alexander A. Razborov:
  Preface. 619
  
• Jirí Fiala, Daniël Paulusma:
  Comparing Universal Covers in Polynomial Time. 620-635
  
• Roman Kuznets:
  Self-Referential Justifications in Epistemic Logic. 636-661
  
• Yury Savateev:
  Unidirectional Lambek Grammars in Polynomial Time. 662-672
  
• Ugo Dal Lago, Martin Hofmann:
  A Semantic Proof of Polytime Soundness of Light Affine Logic. 673-689
  
• Markus Bläser, Holger Dell, Johann A. Makowsky:
  Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions. 690-706
  
• Marius Zimand:
  Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences. 707-722
  
• Mingyu Xiao:
  Simple and Improved Parameterized Algorithms for Multiterminal Cuts. 723-736
  
• Nicolas Bedon, Alexis Bès, Olivier Carton, Chloe Rispal:
  Logic and Rational Languages of Words Indexed by Linear Orderings. 737-760
  
• Uffe Flarup, Laurent Lyaudet:
  On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth. 761-791
  

Last update Sat May 25 20:52:04 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page