President Obama: "Our alliance is founded on shared values and shared interests"
US President Barack Obama and Japanese Prime Minister Yukio Hatoyama have agreed on the need to renew their two countries' strained alliance.
Mr Obama told reporters after talks in Tokyo that their bond was based on shared values and interests but should be renewed for the 21st Century.
Mr Hatoyama said that, after 50 years, the alliance had to adapt to change.
Mr Obama's first Asian tour as US leader is aimed at reassuring key allies and boosting economic growth.
He has called for a growth strategy "that is both balanced and broadly shared".
His eight-day tour will take him to Singapore, China and South Korea and includes an Asia-Pacific Economic Co-operation (Apec) summit.
He told Reuters news agency earlier that China was a "partner" as well as rival but warned of "enormous strains" in relations between the world's two most powerful nations if economic imbalances between them were not corrected.
China will soon overtake Japan as the world's second largest economy, the BBC's Alastair Leithead reports from Tokyo.
The trip is the president's Asian charm offensive as the glitz starts to fade from the year's fashion for Obama-mania, our correspondent says.
The new world order is emerging fast in Asia as the region outgrows decades of American supremacy and the visit is the beginning of a battle to keep the US relevant in the turbulent years of change that lie ahead, he adds.
Friction with Tokyo
Mr Hatoyama confirmed Japan would no longer refuel ships that supply forces in Afghanistan but promised an "alternative package", which would involve civilian aid in areas such as schooling, agriculture and police.
Most of the 47,000 US soldiers in Japan are based on the island
The US military favours Okinawa as it is closer to China and Taiwan
The US governed the island directly for nearly 30 years after World War II
The US wants to move its airbase at Futenma away from residential areas to another location on the island
Pollution from the US bases has angered local people
A number of sexual assaults by US servicemen on Japanese civilians and accidents involving military hardware have fuelled opposition to the bases
Japan's new PM has suggested moving Futenma off the island completely
"I think we have to consider the meaning of this logistical support, and we've come to think there's another type of assistance that is more appropriate for Afghanistan," he said.
He also promised to work with the US to combat climate change and nuclear proliferation.
On the dispute with the US over plans to keep a US air base on the island of Okinawa, albeit in a different location, he said only that the base was a "difficult issue".
Washington thought the issue was settled three years ago but Mr Hatoyama, who came to power this year, has said he wants to review the agreement reached.
Mr Obama said the US and Japan would work quickly to resolve the dispute.
Japanese peace activists have criticised Mr Obama for not taking time to visit Hiroshima and Nagasaki.
Mr Obama said he would visit the sites of the atomic bomb attacks on another occasion.
Japan has deployed about 16,000 police officers to provide security in Tokyo during the visit, which is expected to see further demonstrations.
China's growing economic and military power and its effect on relations with Washington are also concerns for some Japanese.
OBAMA IN ASIA
Friday 13 November: Arrives in Japan
Saturday 14: Leaves Tokyo for Apec summit in Singapore
Sunday 15: Has talks with Russia's President Medvedev among others at the summit before leaving for China
Tuesday 17: Summit in Beijing with Chinese President Hu Jintao
Wednesday 18: Ends tour with visit to South Korea
Three days of the tour are being devoted to the Chinese leg during which Mr Obama hopes to discuss a revaluation of the Chinese currency.
He is also set to discuss opening Chinese markets further to US goods and encouraging Chinese consumers to spend more.
China signalled on Wednesday that it might allow an appreciation of the yuan.
Mr Obama spent several years in Indonesia as a child and is seen as the first president with an "Asia-Pacific orientation", the BBC's Kim Ghattas reports from Washington.
He will try to capitalise on this as he seeks to build on and improve crucial relationships with allies and rivals across the Pacific, our correspondent adds.
Mr Obama stopped off in Alaska on his way, touching down at Elmendorf Air Force Base where he spoke to a military audience about his strategy in Afghanistan.
"I will not risk your lives unless it is necessary to America's vital interests," he told troops.
The US administration has been locked in an intense debate over a request from the American commander in Afghanistan for thousands of extra troops amid doubts over the competence and integrity of the Afghan government.
No decision on the surge request is expected during Mr Obama's visit to Asia, said White House spokesman Robert Gibbs.
Are you in Asia? Will you try to see President Obama when he comes to your country? What do you think of his visit to the region? Send us your comments using the form below.
A selection of your comments may be published, displaying your name and location unless you state otherwise in the box below.
The BBC may edit your comments and not all emails will be published. Your comments may be published on any BBC media worldwide.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.