数学家传记
莱斯利·瓦利安特是一位英美计算机科学家,对理论计算机科学的许多方面做出了基础性贡献。
莱斯利·瓦利安特的父母是瓦利安特和Eva 茹利亚 Ujlaki。他在英格兰长大,就读于北希尔兹的泰恩茅斯高中。这所学校在瓦利安特离开数年后,于1969年更名为诺勒姆高中。瓦利安特在伦敦哈默史密斯国王街的拉蒂默中学完成了他的中学教育。这所学校过去(现在仍然)是一所著名的选拔性独立学校,其声誉可追溯到1624年由Edward Latymer创立之时。从拉蒂默中学毕业后,他进入剑桥大学国王学院学习,获得第一个学位——数学学士学位后,他进入伦敦帝国理工学院学习理论计算机科学。在获得帝国理工学院计算机科学文凭后,瓦利安特前往华威大学,在Michael Stewart Paterson的指导下攻读计算机科学博士学位。
在获得博士学位之前,瓦利安特于1973-74年在美国宾夕法尼亚州匹兹堡的卡内基梅隆大学担任访问助理教授。1974年,他凭借学位论文Decision Procedures for Families of Deterministic Pushdown Automata获得华威大学博士学位。瓦利安特与他的学位论文导师M S Paterson合作,于1973年在波恩向Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen Ⓣ(计算机科学学会自动机理论与形式语言首届研讨会)提交了论文Deterministic one-counter automata。Wilfried Brauer审阅了该论文,写道:-
确定性单计数器自动机(doca)是一种具有单元素栈字母表的确定性下推自动机。容易看出,doca的包含问题和交集为空问题都是不可判定的。与此相反,作者给出了doca等价性的判定过程,并证明其时间复杂度上界为被测doca状态数的平方根左右的指数函数。他们猜想,对于所有确定性下推自动机类,等价性是可判定的。
瓦利安特于1974年发表了论文The equivalence problem for deterministic finite-turn pushdown automata。S A Greibach指出了这篇论文的重要性:
如果下推存储自动机(pda)在任何输入的任何计算过程中,从压入(增加下推存储长度)切换到弹出(减少下推存储长度)的次数有一个统一的界,则称其为有限转向的。作者确立了确定性有限转向pda的等价问题(两台机器是否接受相同的语言?)的可判定性。该结果的重要性在于确立它所用的证明技术,以及它代表了在解决长期悬而未决的猜想——确定性pda(dpda)的等价问题是可判定的——方面的重大突破之一(已知相应问题对于非确定性pda即使是非常受限的情形也是不可判定的)。
1974年从美国返回后,瓦利安特在利兹大学获得讲师职位,并在1974-76两年间在那里工作。让我们再举一个他早期论文的例子,这篇论文同样是与M S Paterson合作撰写的。这篇1975年的论文Deterministic one-counter automata以以下作者引言开头:
我们提出对确定性单计数器自动机的分析,以表明它们的等价问题是可判定的。我们所有的论证和结果都可以直接翻译成模式理论术语。由此得出的推论是,即使允许Janov模式使用辅助计数器,其等价性也是可判定的。
瓦利安特于1975年搬到苏格兰,在爱丁堡大学担任讲师。1977年,他与Gayle Lynne Dyckoff结婚;他们有两个儿子Gregory John Valiant和Paul A 瓦利安特。在爱丁堡,他于1981年被提升为高级讲师,但在1982年前往美国,当时他是哈佛大学的访问教授。那年晚些时候,他被任命为哈佛大学Gordon McKay计算机科学与应用数学教授。他留在哈佛,尽管1987-88学年他在英国牛津大学做访问研究员。2001年,他被任命为哈佛大学工程与应用科学学院的T Jefferson Coolidge计算机科学与应用数学教授。
瓦利安特做出的贡献非常卓越,他因成就获得了最高荣誉。他于1985-86年成为古根海姆研究员,并于1986年获得罗尔夫·内万林纳奖。他于1991年当选为伦敦皇家学会会士,次年当选为美国人工智能协会会士。他于1997年获得美国计算机协会算法与计算理论特别兴趣小组和电气与电子工程师协会计算数学基础技术委员会颁发的高德纳奖。他于2001年当选为美国国家科学院,获得了欧洲理论计算机科学协会奖,以及美国计算机协会2010年艾伦·图灵奖,该奖将于2011年6月4日在加利福尼亚州圣何塞举行的协会年度颁奖宴会上颁发给瓦利安特。该奖项还包括250,000美元的现金奖励。
我们尚未解释瓦利安特因何获得最高奖项的贡献。为此,我们引用伴随艾伦·图灵奖公告的评论(下文引用的2011年文章引用了该评论)。评论开头写道:-
在过去30年中,瓦利安特对理论计算机科学的许多方面做出了基础性贡献。他的工作开辟了新领域,引入了巧妙的新概念,并呈现了极具原创性、深度和美感的结果。瓦利安特的工作一次又一次地真正定义或改变了计算机科学研究的格局。
接着,它详细介绍了瓦利安特做出惊人贡献的几个领域。我们从四个领域中各摘录一些简短片段:
我们以完整引用艾伦·图灵奖引文的结论来结束这篇传记:-
人们很少见到像瓦利安特的工作那样兼具深度与广度的惊人结合。他确实是理论计算机科学中的一位英雄人物,也是以其勇气和创造力处理科学中一些最深未解问题方面的榜样。
尽管我们已经从艾伦·图灵奖的评注中引用了一些篇幅,读者可能仍希望阅读完整的评注。见Valiant's Turing Award Commentary。
Leslie Valiant's parents were Leslie Valiant and Eva Julia Ujlaki. He was brought up in England, attending Tynemouth High School, North Shields. This school was renamed in 1969, several years after Valiant left, when it became known as Norham High School. Valiant completed his school education at Latymer Upper School, in King Street, Hammersmith, London. This was (and still is) a famous selective independent school with a great reputation dating back to its founding by Edward Latymer in 1624. After graduating from Latymer Upper School, he studied at King's College, Cambridge then, after the award of his first degree, a BA in mathematics, he entered Imperial College, London to study theoretical computer science. After the award of the Diploma of the Imperial College in Computer Science, Valiant went to the University of Warwick where he undertook research for a doctorate in computer science with Michael Stewart Paterson as his advisor.
Before the award of his Ph.D., Valiant spent the year 1973-74 in the United States as a Visiting Assistant professor at Carnegie Mellon University in Pittsburgh, Pennsylvania. He was awarded his doctorate by the University of Warwick in 1974 for his thesis Decision Procedures for Families of Deterministic Pushdown Automata. In collaboration with his thesis advisor M S Paterson, Valiant had presented the paper Deterministic one-counter automata to the Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen Ⓣ in Bonn in 1973. Wilfried Brauer reviewed the paper, writing:-
A deterministic one-counter automaton (doca) is a deterministic pushdown automaton having a one-element stack alphabet. It is easy to see that the inclusion and the nullity-of-intersection problems for doca's are undecidable. In contrast to this, the authors give a decision procedure for the equivalence of doca's and show that its time complexity is bounded above by a function exponential in about the square root of the number of states of the tested doca's. They conjecture that the equivalence is decidable for the class of all deterministic pushdown automata.
Valiant published the paper The equivalence problem for deterministic finite-turn pushdown automata in 1974. S A Greibach points out the importance of this paper:-
A pushdown store automaton (pda) is finite-turn if there is a uniform bound on the number of times it can switch from pushing (increasing the length of the pushdown store) to popping (decreasing the pushdown store length) during any computation on any input. The author establishes the decidability of the equivalence problem (do two machines accept the same language?) for deterministic finite-turn pda's. The significance of the result lies in the proof techniques used in establishing it and in the fact that it represents one of the major breakthroughs towards settling the long outstanding conjecture that the equivalence problem for deterministic pda's (dpda's) is decidable (the corresponding problem is known to be undecidable for nondeterministic pda's even in very restricted cases).
After returning from the United States in 1974, Valiant took up a lectureship at Leeds University where he worked for the two years 1974-76. Let us give another example of his early papers, this one again written in collaboration with M S Paterson,. This 1975 paper Deterministic one-counter automata begins with the following authors' introduction:-
We present an analysis of deterministic one-counter automata in order to show that the equivalence problem for them is decidable. All our arguments and results can be translated directly into schema theoretic terms. The corollary that then follows is that equivalence is decidable for Janov schemas even when these are allowed an auxiliary counter.
Valiant moved to Scotland in 1975 to take up a lectureship at the University of Edinburgh. In 1977 he married Gayle Lynne Dyckoff; they had two sons Gregory John Valiant and Paul A Valiant. In Edinburgh he was promoted to reader in 1981 but went to the United States in 1982 when he was a visiting professor at Harvard. Later that year he was appointed Gordon McKay Professor of Computer Science and Applied Mathematics at Harvard. He remained at Harvard, although he spent the year 1987-88 as a visiting fellow at the University of Oxford in England. In 2001 he was named T Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the Harvard School of Engineering and Applied Sciences.
The contributions that Valiant has made are quite remarkable and he has received the highest honours for his achievements. He was a Guggenheim Fellow in 1985-86 and received the Nevanlinna Prize in 1986. He was elected a fellow of the Royal Society of London in 1991 and, in the following year, a fellow of the American Association for Artificial Intelligence. He was awarded the Knuth Prize from the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory and the Institute of Electrical and Electronics Engineers Technical Committee on the Mathematical Foundations of Computing in 1997. He was elected to the United States National Academy of Sciences in 2001, received the European Association for Theoretical Computer Science Award, and the Association for Computing Machinery's 2010 A M Turing Award which will be presented to Valiant at the Association's annual awards banquet in San Jose, California on 4 June 2011. The award also includes a cash prize of $250,000.
We have not explained the contributions by Valiant that have led to him receiving the highest possible awards. To do this we quote from the commentary which accompanies the announcement of the Turing Award (the 2011 articles referenced below quote from that commentary). The commentary begins:-
Over the past 30 years, Leslie Valiant has made fundamental contributions to many aspects of theoretical computer science. His work has opened new frontiers, introduced ingenious new concepts, and presented results of great originality, depth, and beauty. Time and again, Valiant's work has literally defined or transformed the computer science research landscape.
It then goes on the give details of several areas to which Valiant has made stunning contributions. We give some short extracts from each of four areas:
We end this biography by quoting in full the conclusion of the Turing Award citation:-
Rarely does one see such a striking combination of depth and breadth as in Valiant's work. He is truly a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science.
Although we have quoted at some length from the Commentary for the Turing Award, the reader may still wish to read the full commentary. See Valiant's Turing Award Commentary.
正文里的方括号编号指向这里,悬停即可直接看到条目。书目保留原文——译了书名反而查不到文献。
原站列出的延伸阅读与外部数据库,照原样保留,目标多为英文页面。
关于莱斯利·瓦利安特的其它页面:
关于莱斯利·瓦利安特的其它网站:
原站的交叉引用。指向本站已镜像专题的留在站内,其余仍指回原站。