Export

Link to this page

Please use this URL for citations.

Search Other Services

Statistics

  • Access to this page：2,223 times

＜conference paper＞
On the Length of the Minimum Solution of Word Equations in One Variable

Creator
Creator Name
Baba, Kensuke
馬場, 謙介
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院
Creator Name
Tsuruta, Satoshi
鶴田, 聡士
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院
Author PID
K000166
Creator Name
Shinohara, Ayumi
篠原, 歩
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院
Author PID
K000172
Creator Name
Takeda, Masayuki
竹田, 正幸
Affiliation
Affiliation Name
Faculty of Information Science and Electrical Engineering, Kyushu University
九州大学システム情報科学研究院
Language
English
Publisher
Springer
Date
2004-02-19
Source Title
Lecture Notes in Computer Science
Vol
2747
First Page
189
Last Page
197
Publication Type
Accepted Manuscript
Access Rights
open access
Related DOI
Related DOI
Lecture Notes in Computer Science || 2747 || p189-197
http://www.mfcs.sk/mfcs2003/
Related URI
Lecture Notes in Computer Science || 2747 || p189-197
http://www.mfcs.sk/mfcs2003/
Related URI
isIdenticalTo
http://www.springerlink.com/content/4ne13xbfyw7009bk/
Related HDL
Relation
Lecture Notes in Computer Science || 2747 || p189-197
http://www.mfcs.sk/mfcs2003/
Abstract We show the tight upperbound of the length of the minimum solution of a word equation L = R in one variable, in terms of the differences between the positions of corresponding variable occurrences in ...L and R. By introducing the notion of difference, the proof is obtained from Fine and Wilfrsquos theorem. As a corollary, it implies that the length of the minimum solution is less than N = |L|+|R|.show more

Hide fulltext details.

pdf BTST03 pdf 165 KB 348  

Details

Record ID
15558
Peer-Reviewed
Refereed
Related URI
http://www.springerlink.com/content/4ne13xbfyw7009bk/
ISSN
0302-9743
ISBN
978-3-540-40671-6
DOI
10.1007/b11836
Notes
28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003) : August 25-29, 2003 : Bratislava, Slovak Republic
Created Date 2009.10.15
Modified Date 2017.11.10

People who viewed this item also viewed