U.S.-France (INRIA) Cooperative Research: Specifying and Finding Solutions to Constraint and Search Problems

该奖项将支持美国和美国之间的合作研究。 法国计算机科学家 美国调查人员是： C.L.博士刘，爱德华·M博士。Reingold和Nachum医生 德肖维茨，都来自伊利诺伊大学厄巴纳分校。 法国合作者包括：Rene Schott博士，大学 南希、克劳德·基什内尔和迈克尔·鲁辛诺维奇， INRIA洛林校区，法国国家研究所 计算机科学与自动化研究。研究 将集中在约束的算法解决方案和 搜索算法的设计和分析。 设计算法以找到最优或最小值的任务， 问题的近似最优解作为一组约束 从进步所产生的需求中获得了额外的动力 在VLSI电路设计中。 同时，一些现代 编程语言（例如Prolog）可以被视为 搜索指定程序的解决方案的系统， 一系列的限制。 有了并行计算机， 约束求解问题已经出现。 此外，未来 编程环境可能包含内置定理 证明器和约束求解器。 分析技术 需要开发搜索算法。该项目将 解决VSLI研究中的两个主要领域。 设计和 综合领域，大部分工作在短期内进行 将致力于物理设计的研究。从长远 长期以来，调查人员将加强努力， 更高层次的综合领域，特别是 逻辑最小化、模块生成和 国家分配。该项目将受益于广泛的 以及这两个小组在 集成电路的物理设计 存在的问题 被认为将有重要的应用到非常大的 规模集成，非常高级的编程语言， 自动演绎和设计高效的搜索和 约束求解算法 的结果 理论工作将直接有利于我们的能力 为了设计多芯片模块的布线和布局， 这是一个非常重要的概念， 电子公司。

This award will support collaborative research between US and French computer scientists. The US investigators are: Dr. C.L. Liu, Dr. Edward M. Reingold and Dr. Nachum Dershowitz, all from the University of Illinois at Urbana. The French collaborators include: Dr. Rene Schott, University of Nancy and Claude Kirchner and Michael Rusinowitch, of the Lorraine campus of INRIA, the French National Institute for Research in Computer Science and Automation. The research will focus on algorithmic solution of restraints and the design and analysis of search algorithms. The task of designing algorithms for finding optimal or near-optimal solutions to problems as a set of constraints has received added impetus from needs engendered by advances in VLSI circuit design. At the same time, some modern programming languages (e.g. Prolog) can be viewed as systems that search for solutions to programs specified as sets of constraints. With parallel computers, new issues in constraint solving have arisen. Furthermore, future programming environments may contain built in theorem provers and constraint solvers. Techniques for analyzing search algorithms need to be developed. This project will address two major areas in VSLI research. In the design and synthesis area, most of the effort in the short term future will be devoted to research in physical design. In the long term, the investigators will build up their effort in the area of higher level synthesis, in particular, working on topics such as logic minimization, module generation and state assignment. The project will benefit from the extensive and the complementary expertise of the two groups in the physical design of integrated circuits. The problems to be considered will have important applications to very large scale integration, very high level programming languages, automated deduction and design of efficient search and constraint-solution algorithms. The results of the theoretical work will have a direct benefit to our ability to design the wiring and placement of multichip modules, a very important concept which is being exploited by US electronics firms.