What happens to a miner's work when they restart? I am studying the bitcoin internals and especially the proof-of-work. The proof-of-work is based on the mathematical problem that we have to compute from an input that produces a hash with a certain leading substring, I think the substring should start with a certain amount of zeroes.

We hash the current input with SHA-256 so we need to compute 2^256. Now my question is, we hash the previous block chain's hash with transactions and the nonce? Is it anything else including in the hash? Furthermore, if the first try is not successful the nonce is changed as a result to compute a new hash?

A few more questions: 
a) If we start adding transactions to a block and another block is created before our block, what happens to our work? We start mining from the beginning or we continue mining with our remaining transactions?
b) Moreover, can we include blocks with 0 transactions to the block chain?
Now my question is, we hash the previous block chain's hash with transactions and the nonce? 


We can look at the form of a block here. 

The information that is actually hashed include the version, previous block hash, the merkle root of the transactions the miner has included in the block, the current time, the target difficulty of the block, and the 32bit nonce. The rest of the information here is infered. 

There's more information about the block format on the wiki. 


  Furthermore, if the first try is not successful the nonce is changed as a result to compute a new hash?


The nonce is incremented until the 32bit space is exhausted, at which point the header is modified to give a different work for the miner. At the present time this may happen many times a second.  


  If we start adding transactions to a block and another block is created before our block, what happens to our work?


The current work is discarded, and the miner starts working on top of the highest block the know about. 


  Moreover, can we include blocks with 0 transactions to the block chain?


No, a block must contain one transaction containing the miners reward, which can be any value up the limit of the current block reward, at the time of writing this is 25BTC. 1 transaction blocks are quite common, as they're less likely to be orphaned (another is created while the minted block is making it's way across the network).