Abstract
We study the fuzzy extension of FL0 with semantics based on the Gödel t-norm. We show that gfp-subsumption w.r.t. a nite set of primitive denitions can be characterized by a relation on weighted automata, and use this result to provide tight complexity bounds for reasoning in this logic.