@article{Rybalov/10,
AUTHOR = {Rybalov, Alexander N.},
TITLE = {Generic complexity of Presburger arithmetic},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {1},
PAGES = {2-8},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/q43w11256h440488/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Mahajan-Sarma/10,
AUTHOR = {Mahajan, Meena and Sarma, Jayalal M.N.},
TITLE = {On the complexity of matrix rank and rigidity},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {1},
PAGES = {9-26},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/82147270n6863558/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Jez-Okhotin/10b,
AUTHOR = {Je{\.z}, Artur and Okhotin, Alexander},
TITLE = {Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {1},
PAGES = {27-58},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/62363576l871n237/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Babenko/10a,
AUTHOR = {Babenko, Maxim A.},
TITLE = {A fast algorithm for the path 2-packing problem},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {1},
PAGES = {59-79},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/p2r1671vh5450455/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Glasser-Herr-Reitwiessner-Travers-Waldherr/10,
AUTHOR = {Gla{\ss}er, Christian and Herr, Katrin and Reitwie{\ss}ner, Christian and Travers, Stephen and Waldherr, Matthias},
TITLE = {Equivalence problems for circuits over sets of natural numbers},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {1},
PAGES = {80-103},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/006k2602650k48r0/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Hoffmann-Lifshits-Lifshits-Nowotka/10,
AUTHOR = {Hoffmann, Benjamin and Lifshits, Mikhail and Lifshits, Yury and Nowotka, Dirk},
TITLE = {Maximal intersection queries in randomized input models},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {1},
PAGES = {104-119},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/k84np624219t4473/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Cheng-Tarasov-Vyalyi/10,
AUTHOR = {Cheng, Qi and Tarasov, Sergey P. and Vyalyi, Mikhail N.},
TITLE = {Efficient algorithms for sparse cyclotomic integer zero testing},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {1},
PAGES = {120-142},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/n2q3nh1p265880q0/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Buhrman-Fortnow-Koucky-Rogers-Vershchagin/10,
AUTHOR = {Buhrman, Harry and Fortnow, Lance and Kouck{\'y}, Michal and Rogers, John D. and Vershchagin, Nikolay},
TITLE = {Does the polynomial hierarchy collapse if onto functions are invertible?},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {1},
PAGES = {143-156},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/33112812x68210hu/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Asano-Brass-Sasahara/10,
AUTHOR = {Asano, Tetsuo and Brass, Peter and Sasahara, Shinji},
TITLE = {Disc covering problem with application to digital halftoning},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {157-173},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/gn26080118t44253/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Manea-Margenstern-Mitrana-Perez-Jimenez/10,
AUTHOR = {Manea, Florin and Margenstern, Maurice and Mitrana, Victor and P{\'e}rez-Jim{\'e}nez, Mario J.},
TITLE = {A new characterization of $NP, P$ and $P$SPACE with accepting hybrid networks of evolutionary processors},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {174-192},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/865688637337gu63/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Tripathi/10,
AUTHOR = {Tripathi, Rahul},
TITLE = {The 1-versus-2 queries problem revisited},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {193-221},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/48p51071207q670n/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Faliszewski-Ogihara/10,
AUTHOR = {Faliszewski, Piotr and Ogihara, Mitsunori},
TITLE = {On the autoreducibility of functions},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {222-245},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/93v1732187l51378/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Epstein-Imreh-Levin/10a,
AUTHOR = {Epstein, Leah and Imreh, Csan{\'a}d and Levin, Asaf},
TITLE = {Class constrained bin covering},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {246-260},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/jq33475072u7j374/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Damaschke/10a,
AUTHOR = {Damaschke, Peter},
TITLE = {Fixed-parameter enumerability of cluster editing and related problems},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {261-283},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/2u861nn08024g647/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Caminiti-Fusco-Petreschi/10,
AUTHOR = {Caminiti, Saverio and Fusco, Emanuele G. and Petreschi, Rossella},
TITLE = {Bijective linear time coding and decoding for $k$-trees},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {284-300},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/h5732q1544h6135r/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Jukna/10,
AUTHOR = {Jukna, Stasys},
TITLE = {Entropy of operators or why matrix multiplication is hard for depth-two circuits},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {301-310},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/r048k436r53024v4/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Fellows-Flum-Hermelin-Muller-Rosamond/10,
AUTHOR = {Fellows, Michael and Flum, J{\"o}rg and Hermelin, Danny and M{\"u}ller, Moritz and Rosamond, Frances},
TITLE = {$W$-hierarchies defined by symmetric gates},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {311-339},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/hv5208p25725044t/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Andreev-McNicholl/10,
AUTHOR = {Andreev, Valentin V. and McNicholl, Timothy H.},
TITLE = {Computing interpolating sequences},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {340-350},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/9qwx2n5347381g18/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Choffrut-DAlessandro-Varricchio/10,
AUTHOR = {Choffrut, Christian and D'Alessandro, Flavio and Varricchio, Stefano},
TITLE = {On bounded rational trace languages},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {351-369},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/vm0w56103n740053/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Jonsson-Nordh/10,
AUTHOR = {Jonsson, Peter and Nordh, Gustav},
TITLE = {Approximability of clausal constraints},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {2},
PAGES = {370-395},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/c512214665187h87/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Cai-Lu/10a,
AUTHOR = {Cai, Jin-Yi and Lu, Pinyan},
TITLE = {On symmetric signatures in holographic algorithms},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {3},
PAGES = {398-415},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/58387665pv522279/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Czumaj-Sohler/10,
AUTHOR = {Czumaj, Artur and Sohler, Christian},
TITLE = {Small space representations for metric min-sum $k$-clustering and their applications},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {3},
PAGES = {416-442},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/d33v5674382k5035/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Berstel-Boasson-Carton-Fagnot/10,
AUTHOR = {Berstel, Jean and Boasson, Luc and Carton, Olivier and Fagnot, Isabelle},
TITLE = {Sturmian trees},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {3},
PAGES = {443-478},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/n0006l7150484n7q/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Formenti-Kurka-Zahradnik/10,
AUTHOR = {Formenti, Enrico and K{\r{u}}rka, Petr and Zahradn{\'{i}}k, Ond{\v{r}}ej},
TITLE = {A search algorithm for subshift attractors of cellular automata},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {3},
PAGES = {479-498},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/v4676mm568667673/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Limaye-Mahajan-Rao/10,
AUTHOR = {Limaye, Nutan and Mahajan, Meena and Rao, B.V. Raghavendra},
TITLE = {Arithmetizing classes around NC$^1$ and L},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {3},
PAGES = {499-522},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/549100q3h7835601/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Coja-Oghlan-Krivelevich-Vilenchik/10,
AUTHOR = {Coja-Oghlan, Amin and Krivelevich, Michael and Vilenchik, Dan},
TITLE = {Why almost all $k$-colorable graphs are easy to color},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {3},
PAGES = {523-565},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/a835016861860511/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Bodlaender-van_Dijk/10,
AUTHOR = {Bodlaender, Hans L. and van Dijk, Thomas C.},
TITLE = {A cubic kernel for feedback vertex set and loop cutset},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {3},
PAGES = {566-597},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/n622271208527170/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Bienvenu/10,
AUTHOR = {Bienvenu, Laurent},
TITLE = {Kolmogorov-Loveland stochasticity and Kolmogorov complexity},
JOURNAL = {Theory of Computing Systems},
VOLUME = {46},
NUMBER = {3},
PAGES = {598-617},
YEAR = {2010},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/d621808521553p11/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}