As for Nato expansion, one can take an entirely new look at this if Nato takes on a different shade and is becoming a political organisation

President Putin

And there also appeared to be progress in Russia's relationship with Nato.

The alliance's Secretary General, Lord Robertson, said after meeting the Russian president: "These discussions mark a major milestone in the Nato-Russia relationship. We have identified a number of new areas where Nato and Russia can work together," he said.

Mr Putin said earlier Russia would re-consider its hostile position on Nato expansion.

Belgian Prime Minister Guy Verhofstadt, whose country currently holds the rotating EU presidency, told reporters after meeting Mr Putin the EU and Russia would begin to work more closely.

"We have decided now that this should be a structured dialogue with monthly meetings," he said.

Intelligence sharing

It is thought that the European side is hoping for better communications with Russian intelligence authorities and is offering to help with border security and the fight against the illegal arms trade.

Russia says it does not need proof of Bin Laden's guilt

Delighted with Mr Putin's backing for America's global anti-terror coalition, the EU promised it would speed up Russia's entry to the World Trade Organisation.

Mr Putin had arrived in Brussels eager to display support, saying his country needed "no proof of the guilt of Bin Laden" in the devastating September 11 attacks on New York and the Pentagon.

While he has excluded the possibility of Russian military involvement in looming US strikes, he is offering other forms of assistance such as tracking down finances and support networks as well as encouraging former Soviet states to respond to Washington's needs.

Reconsidering

Mr Putin told reporters prior to Wednesday's meeting that he thought it was "time to reflect on the creation of permanent consultative structures in the security field" and said he was ready for "profound" changes in Russia's relations with Nato and EU security bodies.

Putin says Russia will reconsider its opposition to Nato expansion

And after the meeting, Mr Putin said that Russia would go so far as to reconsider its traditional opposition to Nato expansion, if Moscow played a greater role in the process.

Three former Soviet Baltic states are key candidates to join the alliance in another wave of enlargement next year.

"As for Nato expansion, one can take another, an entirely new look at this... if Nato takes on a different shade and is becoming a political organisation," said Mr Putin.

"Of course we would reconsider our position with regard to such expansion if we were to feel involved in such processes."

Chechen rebels

In evocative language Mr Putin described terrorism as a "bacteria" which adapted to and lived off its host states.

Russia says it is fighting terrorists in Chechnya

He also reportedly told his EU colleagues that the breakaway Russian republic of Chechnya was being used as a base for international terrorism.

The BBC's Justin Webb in Brussels says that in the current climate, it is unlikely that EU leaders have pressed Mr Putin on his military action within Chechnya, despite strong pressure from international human rights groups to do so.

The New York-based Human Rights watch has urged the EU to send a strong signal to Russia that recent events did not mean the violations of international law in Chechnya would be tolerated.

Amnesty has demanded an official statement on the physical harm it says is being caused to Chechen civilians.

Although the European Commission has said that nothing has changed in its view of the Chechnya issue, last week German Chancellor Gerhard Schroeder said the Chechen conflict might have to be re-evaluated in the light of what had happened in America.