Cleanup of biomass gasification effluent requires a catalyst that can reform methane and larger hydrocarbons while tolerating the presence of H2S or, ideally, that can act as a sulfur sorbent while reforming hydrocarbons. We utilize density functional theory (DFT) methods to examine the impact of oxide sulfidation on the reforming of methane and the initial steps of propane reforming, using M-doped CeO2 catalysts. On a ceria oxy-sulfide surface, surface oxygen atoms remain active for C-H bond activation via hydride abstraction whereas surface sulfur atoms are significantly less active. Methyl adsorption is slightly favored at a surface sulfur site, and though subsequent dehydrogenation steps remain viable, the final steps of methane decomposition may lead to carbon buildup on the surface. However, surface sulfur sites will be less active globally for the initial rate limiting H abstraction step, and these sites can nucleate carbon buildup. Doping CeO2 with Mn accelerates C-H bond activation, aids eventual CO product desorption, and may induce sulfur tolerance by motivating CH intermediates to bind to surface O atoms rather than surface S atoms. This work represents an initial step in the development of S-tolerant oxide catalysts for hydrocarbon reforming. (C) 2015 Elsevier Inc. All rights reserved.