Ruth Suzanne Zeitman

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Yuri Gurevich

University of Michigan–Ann Arbor

Alexis Manaster Ramer

Wayne State University

Cooperative Institutions

University of Michigan–Ann Arbor

Center for Research and Advanced Studies of the National Polytechnic Institute

Instituto Politécnico Nacional

Microsoft (United States)

Microsoft Research (United Kingdom)

Ben-Gurion University of the Negev

Microsoft Research (India)

Redmond Fire Department

Microsoft Research Asia (China)

Group for Research in Decision Analysis

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

The composition method

Yuri Gurevich Alexis Manaster Ramer Ruth Suzanne Zeitman

The subject of this dissertation is a model-theoretic decidability technique for monadic second-order theories. This technique, which we call the composition method, was used by Saharon Shelah and Yuri Gurevich to extend decidability results for linear orders in some sense as far as possible. Many properties of structures that are of importance in computer science are expressible in monadic second-order logic. There is an close connection between this logic and the theory of finite automata and regular languages. Unfortunately, the composition method has remained relatively unknown. Part of the purpose of this dissertation is to present the technique in an accessible manner, and to show that it provides a clarifying and unifying approach to many decision problems. This is done in part by giving new applications of the technique to problems for which other and varied methods have been developed. Two of these applications concern classes of graphs whose tree-width is bounded by some fixed number, and are novel uses of the composition method in the sense that they allow identification of elements in components of the composition. We also give a new general template for the use of the method (which allows for the identification mentioned above) in the form of theorems that give sufficient conditions for its application.

Tree automaton

Source

Cite

Citations (7)