I can say 歩いて渡る which translates to "to cross by walking". However, if I would like to say "I am not going to cross by walking, but by some other means", would I say 歩かないで渡る or 歩いて渡らない?
There are many other examples, most of which involve the use of the so-called Japanese auxilary verbs that follow the te-form of the verb they "help" (ある, いる, くれる, あげる, もらう, 行く, 来る, etc). I don't like this term because I view them as just normal verbs.
Another example would be 食べている. To say that "(I) am not eating", it would be 食べていない instead of the more logical structure 食べないでいる, which would, at least in my opinion, nicely and logically translate to "I am not in the state of eating". This is because the verb that needs the negation is the verb 食べる, not the verb いる.
Explanations from linguistic points of view are also welcome.
I hate to treat this kind of verbs as auxiliary verbs. They are just verbs chained together using serial verb construction, which exists in a number of East Asian languages (Korean, Chinese, Thai, Vietnamese, etc), and at least in my first language, I would treat them as normal verbs chained together to indicate:
(1) a sequence of actions happening one after another
(2) a set of actions happening simultaneously as in 歩いて渡る and 食べている
(4) method as in 歩いて渡る
So the concept is pretty much the same, except for the fact that in Japanese these verbs are "special" when it comes to negation.