It said they agreed to work "to clear the atmosphere and settle the conflict between the Republic of Sudan and Eritrea, as part of the mediation undertaken by Qatar."

The Qatari emir, Sheikh Hamad ibn Khalifa al-Thani, attended the signing, QNA said without giving details of the accord. The two presidents later left Doha.

Asmara has hosted the main Sudanese opposition coalition, the National Democratic Alliance, since 1996 and Khartoum routinely accuses it of providing the coalition's armed wing with military support.

Asmara denies the charge and in turn accuses Khartoum, which in early March brokered the creation of a united Eritrean opposition front, of providing its opponents with armed support.

On Saturday, Issaias said his country was "completely convinced of the need to go beyond the mistakes made in the past, and circumstances now favour a normalisation."

Qatar has been mediating for several months between Eritrea and Sudan, which severed diplomatic relations in December 1994.

Issaias said Doha's ideas were based on "creating a climate of stability and security throughout the Horn of Africa in order to enable the countries of the region to exploit their resources."

In Khartoum, meanwhile, a senior official of the ruling National Congress Party reiterated a list of conditions.

He said Khartoum expected Asmara to abandon plans to topple the Sudanese government by force, stop the opposition launching raids into eastern Sudan from Eritrean territory, and hand back the embassy building in Asmara which is currently in opposition hands.

"Issaias should display goodwill and sincerity for normalisation of his ties with Sudan so as not to allow his acceptance of the Qatar-Libyan initiative to be interpreted as a break or a temporary truce," said Abdallah Suleiman al-Awad, the ruling party's external relations secretary.

An armed north Sudanese opposition group, the Sudan Alliance Forces, announced Sunday that its fighters had killed five Sudanese soldiers and wounded three in an attack on army barracks close to the Eritrean border.

The target of the attack was the Laffah barracks, 13 kilometres (eight miles) from the eastern town of Kassala, the group said in a statement faxed to AFP in Cairo.

Libya has also been playing a key role in the mediation between Asmara and Khartoum.

The sources said that the fighting took place inside Baidoa and on two other fronts, but most of the dead were killed inside Baidoa.

In the counter-attack, a force led by Aidid himself recaptured Baidoa from the Rahanwein Resistance Army (RRA), which had seized the town from Aidid's militia forces late Saturday afternoon.

Top RRA officials confirmed the new power-shift in Baidoa, saying that most of those killed were Aidid fighters, and several civilians caught in crossfire.

The latest fighting brought the death toll in the fighting for control of Baidoa to 40 and 69 wounded since Saturday.

RRA commander Colonel Mohamed Hassan Shatigudud announced here on Sunday morning that his men had seized Baidoa and neighbouring villages late Saturday afternoon from Aidid in a "sweeping, carefully planned operation."

The attack on Baidoa, 250 kilometres (155 miles) west of Mogadishu, had coincided with the announcement by elders of the seizure of another southern town of Luuq in Gedo region by Ethiopian troops, backed by a faction within the rift-ridden Marehan-dominated Somali National Front (SNF).

But the SNF faction, led by Mohamed Sheikh Ali Ahmed, which now controls Luuq, on Sunday denied Ethiopian envolvement in the capture of the southern town near the Kenyan-Ethiopian border.

Observers here had earlier on Sunday expressed doubts that the RRA would sustain their capture of Baidoa, noting that in the past three years the RRA had captured the town several times, only to lose it again to Aidid's forces.

The capture of Baidoa had been seen here as a major military setback for Aidid's faction, which has repeatedly rejected calls from various factions to withdraw his gunmen from the town, captured in 1995 by his father, the late General Mohamed Farah Aidid.

With over half a million troops deployed along the disputed border and tens of thousands of casualties in the fighting so far this year, the Ethiopia-Eritrea war is the world's biggest war - although most of the world doesn't seem to have noticed. Modern weapons have been used with the trench tactics of World War I - heavy artillery barrages, followed by infantry assaults (with tank support where possible) and air attacks. In February at Badme, Ethiopian commanders expected and accepted heavy casualties, attacking fixed positions which the Eritrean forces had spent ten months preparing. Neither side has given a figure for its own losses; neither has allowed access by the International Committee of the Red Cross to the wounded or to prisoners. At Badme, casualties appear to have been roughly 15,000-20,000 on each side, though many more Eritreans were taken prisoner than Ethiopians, and more Ethiopians died than Eritreans.

RRA spokesman Mohamed Aden Qalinle charged that 450 Ethiopian Oromo Liberation Front (OLF) fighters were being trained to carry out hit-and-run raids inside Ethiopia.

"There are six Eritrean trainers and a dozen Somali military officers trained in the former Soviet Union and Arab countries training the Oromo guerrillas in camps in Qoryoley district in Somalia's southern Lower Shabelle region," Qalinle said.

Qalinle said explosions had been heard repeatedly by residents of the region at night, and that information gathered secretly from the scene indicated that "only 76 people were being trained at a time."

Qalinle's accusations could not be independently verified, but western diplomats here backed up the charges, noting an escalation of arms shipments to rival Somali factions from Eritrea and Ethiopia since the outbreak of the border war between them in May last year.

Ethiopian diplomats here said they were following the situation in Qoryoley and would take seriously any reports of military training inside Somalia for Ethiopians rebels.

Eritrean embassy press attache, Kidane Woldeyesus, meanwhile denied the charge, accusing Ethiopia of habitually blaming others for internal problems involving its 83 opposing ethnic groups.

"A country with 3,000 years of independence was sitting like a lame duck, only invading neighbours instead of competing economically with the United States and other developed countries," Woldeyesus charged, adding: "Somalia and Eritrea are victims of the ruling Tigre Popular Liberation Front attacks."

The Ethiopian government has repeatedly accused the OLF of fighting it from bases inside neighbouring Kenya and Somalia since last year.

Somali factions have accused Eritrea and Ethiopia, both members of the regional Inter-Governmental Authority on Development (IGAD), of arming them against each other.

"IGAD member states at war are undermining IGAD's capacity to respond to long-existing problems, such as Somalia," Kenyan Foreign Minister Bonaya Godana was recently quoted as having told a UN news bulletin.

According to the bulletin, Godana reported suspicions that both Asmara and Addis Ababa had their own client groups in Somalia.

Somalia's armed Islamic group, Al-Itihad al-Islam, and Ethiopian rebel groups have recently vowed to topple the Addis Ababa government, forcing Kenya to boost its military strength at the three country's common borders.

Godana said his government was aware of, but not alarmed by, the presence in Somalia of the group, accused of the March 20 killing of Kenyan-based US aid worker Deena Marie Umbarger at the Somali border town of Kiabmoni.