Siu Fai Keung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 79-83). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- (Weighted) Constraint Satisfaction --- p.1 / Chapter 1.2 --- Set Variables --- p.2 / Chapter 1.3 --- Motivations and Goals --- p.3 / Chapter 1.4 --- Overview of the Thesis --- p.4 / Chapter 2 --- Background --- p.6 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.6 / Chapter 2.1.1 --- Backtracking Tree Search --- p.8 / Chapter 2.1.2 --- Consistency Notions --- p.10 / Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.14 / Chapter 2.2.1 --- Branch and Bound Search --- p.17 / Chapter 2.2.2 --- Consistency Notions --- p.19 / Chapter 2.3 --- Classical CSPs with Set Variables --- p.23 / Chapter 2.3.1 --- Set Variables and Set Domains --- p.24 / Chapter 2.3.2 --- Set Constraints --- p.24 / Chapter 2.3.3 --- Searching with Set Variables --- p.26 / Chapter 2.3.4 --- Set Bounds Consistency --- p.27 / Chapter 3 --- Weighted Constraint Satisfaction with Set Variables --- p.30 / Chapter 3.1 --- Set Variables --- p.30 / Chapter 3.2 --- Set Domains --- p.31 / Chapter 3.3 --- Set Constraints --- p.31 / Chapter 3.3.1 --- Zero-arity Constraint --- p.33 / Chapter 3.3.2 --- Unary Constraints --- p.33 / Chapter 3.3.3 --- Binary Constraints --- p.36 / Chapter 3.3.4 --- Ternary Constraints --- p.36 / Chapter 3.3.5 --- Cardinality Constraints --- p.37 / Chapter 3.4 --- Characteristics --- p.37 / Chapter 3.4.1 --- Space Complexity --- p.37 / Chapter 3.4.2 --- Generalization --- p.38 / Chapter 4 --- Consistency Notions and Algorithms for Set Variables --- p.41 / Chapter 4.1 --- Consistency Notions --- p.41 / Chapter 4.1.1 --- Element Node Consistency --- p.41 / Chapter 4.1.2 --- Element Arc Consistency --- p.43 / Chapter 4.1.3 --- Element Hyper-arc Consistency --- p.43 / Chapter 4.1.4 --- Weighted Cardinality Consistency --- p.45 / Chapter 4.1.5 --- Weighted Set Bounds Consistency --- p.46 / Chapter 4.2 --- Consistency Enforcing Algorithms --- p.47 / Chapter 4.2.1 --- "Enforcing Element, Node Consistency" --- p.48 / Chapter 4.2.2 --- Enforcing Element Arc Consistency --- p.51 / Chapter 4.2.3 --- Enforcing Element Hyper-arc Consistency --- p.52 / Chapter 4.2.4 --- Enforcing Weighted Cardinality Consistency --- p.54 / Chapter 4.2.5 --- Enforcing Weighted Set Bounds Consistency --- p.56 / Chapter 5 --- Experiments --- p.59 / Chapter 5.1 --- Modeling Set Variables Using 0-1 Variables --- p.60 / Chapter 5.2 --- Softening the Problems --- p.61 / Chapter 5.3 --- Steiner Triple System --- p.62 / Chapter 5.4 --- Social Golfer Problem --- p.63 / Chapter 5.5 --- Discussions --- p.66 / Chapter 6 --- Related Work --- p.68 / Chapter 6.1 --- Other Consistency Notions in WCSPs --- p.68 / Chapter 6.1.1 --- Full Directional Arc Consistency --- p.68 / Chapter 6.1.2 --- Existential Directional Arc Consistency --- p.69 / Chapter 6.2 --- Classical CSPs with Set Variables --- p.70 / Chapter 6.2.1 --- Bounds Reasoning --- p.70 / Chapter 6.2.2 --- Cardinality Reasoning --- p.70 / Chapter 7 --- Concluding Remarks --- p.72 / Chapter 7.1 --- Contributions --- p.72 / Chapter 7.2 --- Future Work --- p.74 / List of Symbols --- p.76 / Bibliography --- p.79

Woo Hiu Chun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 91-99). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Weighted Constraint Satisfaction Problems --- p.3 / Chapter 1.3 --- Redundant Modeling --- p.4 / Chapter 1.4 --- Motivations and Goals --- p.5 / Chapter 1.5 --- Outline of the Thesis --- p.6 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.8 / Chapter 2.1.1 --- Backtracking Tree Search --- p.9 / Chapter 2.1.2 --- Local Consistencies --- p.12 / Chapter 2.1.3 --- Local Consistencies in Backtracking Search --- p.17 / Chapter 2.1.4 --- Permutation CSPs --- p.19 / Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.20 / Chapter 2.2.1 --- Branch and Bound Search --- p.23 / Chapter 2.2.2 --- Local Consistencies --- p.26 / Chapter 2.2.3 --- Local Consistencies in Branch and Bound Search --- p.32 / Chapter 2.3 --- Redundant Modeling --- p.34 / Chapter 3 --- Generating Redundant WCSP Models --- p.37 / Chapter 3.1 --- Model Induction for CSPs --- p.38 / Chapter 3.1.1 --- Stated Constraints --- p.39 / Chapter 3.1.2 --- No-Double-Assignment Constraints --- p.39 / Chapter 3.1.3 --- At-Least-One-Assignment Constraints --- p.40 / Chapter 3.2 --- Generalized Model Induction for WCSPs --- p.43 / Chapter 4 --- Combining Mutually Redundant WCSPs --- p.47 / Chapter 4.1 --- Naive Approach --- p.47 / Chapter 4.2 --- Node Consistency Revisited --- p.51 / Chapter 4.2.1 --- Refining Node Consistency Definition --- p.52 / Chapter 4.2.2 --- Enforcing m-NC* c Algorithm --- p.55 / Chapter 4.3 --- Arc Consistency Revisited --- p.58 / Chapter 4.3.1 --- Refining Arc Consistency Definition --- p.60 / Chapter 4.3.2 --- Enforcing m-AC*c Algorithm --- p.62 / Chapter 5 --- Experiments --- p.67 / Chapter 5.1 --- Langford's Problem --- p.68 / Chapter 5.2 --- Latin Square Problem --- p.72 / Chapter 5.3 --- Discussion --- p.75 / Chapter 6 --- Related Work --- p.77 / Chapter 6.1 --- Soft Constraint Satisfaction Problems --- p.77 / Chapter 6.2 --- Other Local Consistencies in WCSPs --- p.79 / Chapter 6.2.1 --- Full Arc Consistency --- p.79 / Chapter 6.2.2 --- Pull Directional Arc Consistency --- p.81 / Chapter 6.2.3 --- Existential Directional Arc Consistency --- p.82 / Chapter 6.3 --- Redundant Modeling and Channeling Constraints --- p.83 / Chapter 7 --- Concluding Remarks --- p.85 / Chapter 7.1 --- Contributions --- p.85 / Chapter 7.2 --- Future Work --- p.87 / List of Symbols --- p.88 / Bibliography

Lam Yee Gordon. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 109-117). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Motivations and Goals --- p.2 / Chapter 1.3 --- Outline of the Thesis --- p.4 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- CSP --- p.5 / Chapter 2.2 --- Classes of Variable --- p.6 / Chapter 2.3 --- Solution of a CSP --- p.7 / Chapter 2.4 --- Constraint Solving Techniques --- p.8 / Chapter 2.4.1 --- Local Consistencies --- p.8 / Chapter 2.4.2 --- Constraint Tightness --- p.10 / Chapter 2.4.3 --- Tree Search --- p.10 / Chapter 2.5 --- Graph --- p.14 / Chapter 3 --- Common Channeling Constraints --- p.16 / Chapter 3.1 --- Models --- p.16 / Chapter 3.2 --- Channeling Constraints --- p.17 / Chapter 3.2.1 --- Int-Int Channeling Constraint (II) --- p.18 / Chapter 3.2.2 --- Set-Int Channeling Constraint (SI) --- p.21 / Chapter 3.2.3 --- Set-Set Channeling Constraint (SS) --- p.24 / Chapter 3.2.4 --- Int-Bool Channeling Constraint (IB) --- p.25 / Chapter 3.2.5 --- Set-Bool Channeling Constraint (SB) --- p.27 / Chapter 3.2.6 --- Discussions --- p.29 / Chapter 4 --- Realization in Existing Solvers --- p.31 / Chapter 4.1 --- Implementation by if-and-only-if constraint --- p.32 / Chapter 4.1.1 --- "Realization of iff in CHIP, ECLiPSe, and SICStus Prolog" --- p.32 / Chapter 4.1.2 --- Realization of iff in Oz and ILOG Solver --- p.32 / Chapter 4.2 --- Implementations by Element Constraint --- p.38 / Chapter 4.2.1 --- "Realization of ele in CHIP, ECLiPSe, and SICStus Prolog" --- p.40 / Chapter 4.2.2 --- Realization of ele in Oz and ILOG Solver --- p.40 / Chapter 4.3 --- Global Constraint Implementations --- p.41 / Chapter 4.3.1 --- "Realization of glo in CHIP, SICStus Prolog, and ILOG Solver" --- p.42 / Chapter 5 --- Consistency Levels --- p.43 / Chapter 5.1 --- Int-Int Channeling (II) --- p.44 / Chapter 5.2 --- Set-Int Channeling (SI) --- p.49 / Chapter 5.3 --- Set-Set Channeling Constraints (SS) --- p.53 / Chapter 5.4 --- Int-Bool Channeling (IB) --- p.55 / Chapter 5.5 --- Set-Bool Channeling (SB) --- p.57 / Chapter 5.6 --- Discussion --- p.59 / Chapter 6 --- Algorithms and Implementation --- p.61 / Chapter 6.1 --- Source of Inefficiency --- p.62 / Chapter 6.2 --- Generalized Element Constraint Propagators --- p.63 / Chapter 6.3 --- Global Channeling Constraint --- p.66 / Chapter 6.3.1 --- Generalization of Existing Global Channeling Constraints --- p.66 / Chapter 6.3.2 --- Maintaining GAC on Int-Int Channeling Constraint --- p.68 / Chapter 7 --- Experiments --- p.72 / Chapter 7.1 --- Int-Int Channeling Constraint --- p.73 / Chapter 7.1.1 --- Efficient AC implementations --- p.74 / Chapter 7.1.2 --- GAC Implementations --- p.75 / Chapter 7.2 --- Set-Int Channeling Constraint --- p.83 / Chapter 7.3 --- Set-Set Channeling Constraint --- p.89 / Chapter 7.4 --- Int-Bool Channeling Constraint --- p.89 / Chapter 7.5 --- Set-Bool Channeling Constraint --- p.91 / Chapter 7.6 --- Discussion --- p.93 / Chapter 8 --- Related Work --- p.101 / Chapter 8.1 --- Empirical Studies --- p.101 / Chapter 8.2 --- Theoretical Studies --- p.102 / Chapter 8.3 --- Applications --- p.103 / Chapter 8.4 --- Other Kinds of Channeling Constraints --- p.104 / Chapter 9 --- Concluding Remarks --- p.106 / Chapter 9.1 --- Contributions --- p.106 / Chapter 9.2 --- Future Work --- p.108 / Bibliography --- p.109

by Wong, Yin Pong Anthony. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 101-107). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.2 / Chapter 1.2 --- Solution Stability in Dynamic Constraint Satisfaction Problems --- p.3 / Chapter 1.3 --- Motivation of the Research --- p.5 / Chapter 1.4 --- Overview of the Thesis --- p.5 / Chapter 2 --- Related Work --- p.7 / Chapter 2.1 --- Complete Search Algorithms --- p.7 / Chapter 2.1.1 --- DnAC-4 --- p.8 / Chapter 2.1.2 --- ac --- p.9 / Chapter 2.1.3 --- DnAC-6 --- p.9 / Chapter 2.2 --- Algorithms for Stability --- p.10 / Chapter 2.2.1 --- Bellicha --- p.10 / Chapter 2.2.2 --- Dynamic Dynamic Backtracking --- p.11 / Chapter 2.2.3 --- Wallace and Freuder --- p.12 / Chapter 2.2.4 --- Unimodular Probing --- p.13 / Chapter 2.2.5 --- Train Rescheduling --- p.14 / Chapter 2.3 --- Constrained Optimization Algorithms --- p.14 / Chapter 2.3.1 --- Guided Local Search --- p.14 / Chapter 2.3.2 --- Anytime CSA with Iterative Deepening --- p.15 / Chapter 2.4 --- A Real-life Application --- p.16 / Chapter 3 --- Background --- p.17 / Chapter 3.1 --- Fuzzy Constraint Satisfaction Problems --- p.17 / Chapter 3.2 --- Fuzzy GENET --- p.19 / Chapter 3.2.1 --- Network Architecture --- p.19 / Chapter 3.2.2 --- Convergence Procedure --- p.21 / Chapter 3.3 --- Deficiency in Fuzzy GENET --- p.24 / Chapter 3.4 --- Rectification of Fuzzy GENET --- p.26 / Chapter 4 --- Using Fuzzy GENET for Solving Stability Problems --- p.30 / Chapter 4.1 --- Modelling Stability Problems as FCSPs --- p.30 / Chapter 4.2 --- Extending Fuzzy GENET for Solving Stability Problems --- p.36 / Chapter 4.3 --- Experiments --- p.38 / Chapter 4.3.1 --- Dynamic CSP Generation --- p.39 / Chapter 4.3.2 --- Problems Using Hamming Distance Function --- p.41 / Chapter 4.3.2.1 --- Variation in Number of Variables --- p.42 / Chapter 4.3.2.2 --- Variation in Domain Size --- p.45 / Chapter 4.3.2.3 --- Variation in Density and Tightness --- p.47 / Chapter 4.3.3 --- Comparison in Using Different Thresholds --- p.47 / Chapter 4.3.4 --- Problems Using Manhattan Distance Function --- p.50 / Chapter 5 --- Enhancement of the Modelling Scheme --- p.56 / Chapter 5.1 --- Distance Bound --- p.56 / Chapter 5.2 --- Enhancement of Convergence Procedure --- p.57 / Chapter 5.3 --- Comparison with Optimal Solutions --- p.60 / Chapter 5.4 --- Comparison with Fuzzy GENET(dcsp) --- p.64 / Chapter 5.4.1 --- Medium-sized Problems --- p.64 / Chapter 5.4.2 --- The 150-10-15-15 Problem --- p.67 / Chapter 5.4.3 --- Variation in Density and Tightness --- p.73 / Chapter 5.4.4 --- Variation in Domain Size --- p.76 / Chapter 5.5 --- Analysis of Fuzzy GENET(dcsp2) --- p.94 / Chapter 6 --- Conclusion --- p.98 / Chapter 6.1 --- Contributions --- p.98 / Chapter 6.2 --- Future Work --- p.99 / Bibliography --- p.101

Law Yat Chiu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 85-89). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Related Work --- p.4 / Chapter 2.1 --- Equivalence of CSPs --- p.4 / Chapter 2.2 --- Dual Viewpoint --- p.4 / Chapter 2.3 --- CSP Reformulation --- p.5 / Chapter 2.4 --- Multiple Modeling --- p.5 / Chapter 2.5 --- Redundant Modeling --- p.6 / Chapter 2.6 --- Minimal Combined Model --- p.6 / Chapter 2.7 --- Permutation CSPs and Channeling Constraints --- p.6 / Chapter 3 --- Background --- p.8 / Chapter 3.1 --- From Viewpoints to CSP Models --- p.8 / Chapter 3.2 --- Constraint Satisfaction Techniques --- p.10 / Chapter 3.2.1 --- Backtracking Search --- p.11 / Chapter 3.2.2 --- Consistency Techniques and Constraint Propagation --- p.12 / Chapter 3.2.3 --- Incorporating Consistency Techniques into Backtracking Search --- p.18 / Chapter 4 --- Model Induction --- p.21 / Chapter 4.1 --- Channeling Constraints --- p.21 / Chapter 4.2 --- Induced Models --- p.22 / Chapter 4.3 --- Properties --- p.30 / Chapter 5 --- Exploiting Redundancy from Model Induction --- p.35 / Chapter 5.1 --- Combining Redundant Models --- p.35 / Chapter 5.1.1 --- Model Intersection --- p.36 / Chapter 5.1.2 --- Model Channeling --- p.38 / Chapter 5.2 --- Three New Forms of Model Redundancy --- p.39 / Chapter 5.3 --- Experiments --- p.42 / Chapter 5.3.1 --- Langford's Problem --- p.44 / Chapter 5.3.2 --- Random Permutation CSPs --- p.53 / Chapter 5.3.3 --- Golomb Rulers --- p.72 / Chapter 5.3.4 --- Circular Golomb Rulers --- p.74 / Chapter 5.3.5 --- All-Interval Series Problem --- p.78 / Chapter 6 --- Concluding Remarks --- p.82 / Chapter 6.1 --- Contributions --- p.82 / Chapter 6.2 --- Future Work --- p.83

A widely adopted approach to solving constraint satisfaction problems combines backtracking tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model and may offer extra information to enhance constraint propagation. However, some redundant constraints are propagation redundant and hence do not contribute additional propagation information to the constraint solver. In this thesis, we propose propagation rules as a tool to compare the propagation strength of constraints, and establish results relating logical and propagation redundancy. / Redundant constraints arise naturally in the process of redundant modeling, where two models of the same problem are connected and combined through channeling constraints. We characterize channeling constraints in terms of restrictive and unrestrictive channel function and give general theorems for proving propagation redundancy of constraints in the combined model. We illustrate, on problems from CSPLib, how detecting and removing propagation redundant constraints can often significantly speed up constraint-solving. / Choi Chiu Wo. / "September 2005." / Adviser: Jimmy Lee. / Source: Dissertation Abstracts International, Volume: 67-07, Section: B, page: 3890. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (p. 106-117). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

Wu, Yi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 74-80). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Weighted Constraint Satisfaction Problems --- p.3 / Chapter 1.3 --- Motivation and Goal --- p.4 / Chapter 1.4 --- Outline of the Thesis --- p.5 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.7 / Chapter 2.1.1 --- Backtracking Tree search --- p.8 / Chapter 2.1.2 --- Local consistencies in CSP --- p.11 / Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.18 / Chapter 2.2.1 --- Branch and Bound Search --- p.20 / Chapter 2.2.2 --- Local Consistencies in WCSP --- p.21 / Chapter 2.3 --- Global Constraints --- p.31 / Chapter 3 --- Tractable Projection-Safety --- p.36 / Chapter 3.1 --- Tractable Projection-Safety: Definition and Analysis --- p.37 / Chapter 3.2 --- Polynomially Decomposable Soft Constraints --- p.42 / Chapter 4 --- Examples of Polynomially Decomposable Soft Global Constraints --- p.48 / Chapter 4.1 --- Soft Among Constraint --- p.49 / Chapter 4.2 --- Soft Regular Constraint --- p.51 / Chapter 4.3 --- Soft Grammar Constraint --- p.54 / Chapter 4.4 --- Max_Weight/Min Weight Constraint --- p.57 / Chapter 5 --- Experiments --- p.61 / Chapter 5.1 --- The car Sequencing Problem --- p.61 / Chapter 5.2 --- The nonogram problem --- p.62 / Chapter 5.3 --- Well-Formed Parenthesis --- p.64 / Chapter 5.4 --- Minimum Energy Broadcasting Problem --- p.64 / Chapter 6 --- Related Work --- p.67 / Chapter 6.1 --- WCSP Consistencies --- p.67 / Chapter 6.2 --- Global Constraints . --- p.68 / Chapter 7 --- Conclusion --- p.71 / Chapter 7.1 --- Contributions --- p.71 / Chapter 7.2 --- Future Work --- p.72 / Bibliography --- p.74

by Yuen Siu Ming. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 104-110). / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.4 / Chapter 2.1 --- Approaches in Formal Hardware Verification --- p.4 / Chapter 2.1.1 --- Theorem Proving --- p.5 / Chapter 2.1.2 --- Symbolic Simulation --- p.5 / Chapter 2.1.3 --- Model Checking --- p.6 / Chapter 2.2 --- Temporal Theories --- p.7 / Chapter 2.3 --- Related Works --- p.8 / Chapter 2.3.1 --- Consistency and Satisfiability of Timing Specifications --- p.8 / Chapter 2.3.2 --- Symbolic Constraint Satisfaction --- p.9 / Chapter 3 --- Problem Domain --- p.11 / Chapter 3.1 --- Basics of MC68000 Read Cycle --- p.11 / Chapter 4 --- Knowledge-based System Structure --- p.13 / Chapter 4.1 --- Diagnostic Reasoning Mechanisms --- p.14 / Chapter 4.2 --- Occurring Event Sequence --- p.16 / Chapter 4.3 --- Equivalent Goals --- p.17 / Chapter 4.4 --- CPU Databus Setup Time --- p.17 / Chapter 4.5 --- Assertion of CPU AS Signal --- p.19 / Chapter 5 --- Time Range Approach --- p.21 / Chapter 5.1 --- Time Range Represent ation --- p.21 / Chapter 5.2 --- Time Ranges Reasoning Techniques --- p.22 / Chapter 5.2.1 --- Constraint Satisfaction of Time Ranges --- p.22 / Chapter 5.2.2 --- Constraint Propagation of Time Ranges --- p.25 / Chapter 5.3 --- Worst-Case Timing Analysis --- p.28 / Chapter 5.4 --- System Implementation --- p.29 / Chapter 5.4.1 --- CPU Databus Setup Time --- p.30 / Chapter 5.4.2 --- Assertion of CPU AS Signal --- p.36 / Chapter 5.5 --- Implementation Results --- p.40 / Chapter 5.5.1 --- CPU Databus Setup Time --- p.40 / Chapter 5.5.2 --- Assertion of CPU AS Signal --- p.40 / Chapter 5.6 --- Conclusion --- p.41 / Chapter 6 --- Fuzzy Time Point Approach --- p.43 / Chapter 6.1 --- Fuzzy Time Point Models --- p.44 / Chapter 6.1.1 --- Concept of Fuzzy Numbers --- p.44 / Chapter 6.1.2 --- Definition of Fuzzy Time Points --- p.45 / Chapter 6.1.3 --- Semi-bounded Fuzzy Time Points --- p.47 / Chapter 6.2 --- Fuzzy Time Point Reasoning Techniques --- p.48 / Chapter 6.2.1 --- Constraint Propagation of Fuzzy Time Points --- p.50 / Chapter 6.2.2 --- Constraint Satisfaction of Fuzzy Time Points --- p.52 / Chapter 6.3 --- System Implementation --- p.55 / Chapter 6.3.1 --- Representation of Fuzzy Time Point --- p.55 / Chapter 6.3.2 --- Fuzzy Time Point Satisfaction --- p.56 / Chapter 6.3.3 --- Fuzzy Time Point Propagation --- p.58 / Chapter 6.4 --- Implementation Results --- p.64 / Chapter 6.4.1 --- CPU Databus Setup Time --- p.64 / Chapter 6.4.2 --- Assertion of CPU AS Signal --- p.65 / Chapter 6.5 --- Fuzzy Time Point Model Parameters --- p.66 / Chapter 6.5.1 --- Variation of Semi-bounded ftps' Membership Function --- p.66 / Chapter 6.5.2 --- Variation of μftp --- p.67 / Chapter 6.5.3 --- Variation of K --- p.69 / Chapter 6.6 --- Conclusion --- p.69 / Chapter 7 --- Constraint Compatibility Reasoning --- p.72 / Chapter 7.1 --- Abstract Timing Parameters --- p.73 / Chapter 7.2 --- MC68000 Read Cycle: Wait States Insertion --- p.75 / Chapter 7.3 --- Constraint Compatibility of Fuzzy Time Point --- p.75 / Chapter 7.3.1 --- Crisp Threshold Value --- p.77 / Chapter 7.3.2 --- Possibility Quantification for the Number of Wait States --- p.78 / Chapter 7.3.3 --- Threshold Beyond Fuzzy Time Point --- p.80 / Chapter 7.3.4 --- Fuzzy Time Point Beyond Threshold --- p.80 / Chapter 7.3.5 --- Threshold Within Fuzzy Time Point --- p.82 / Chapter 7.4 --- Determine When CPU Clock State is S5 --- p.83 / Chapter 7.5 --- System Implementation --- p.84 / Chapter 7.5.1 --- Expert's Heuristic Rule --- p.84 / Chapter 7.5.2 --- Constraint Compatibility --- p.85 / Chapter 7.5.3 --- Wait States Insertion --- p.87 / Chapter 7.6 --- Implementation Results --- p.91 / Chapter 7.7 --- Conclusion --- p.93 / Chapter 8 --- Conclusion --- p.95 / Chapter 8.1 --- Applications in Other Domains --- p.97 / Chapter 8.2 --- Future Directions and Recommendations --- p.98 / Chapter A --- Constraint Compatibility Reasoning Output --- p.99 / Chapter A.1 --- No Wait Cycle Insertion --- p.99 / Chapter A.2 --- Single Wait Cycle Insertion --- p.100 / Chapter A.3 --- Two Wait Cycle Insertions --- p.100 / Chapter B --- MC68020 Read Cycle Problem --- p.101 / Chapter B.1 --- Basics of MC68020 Read Cycle --- p.101 / Chapter B.2 --- MC68020 Databus Setup Time --- p.102 / Chapter B.3 --- Implementation Results --- p.103 / Bibliography --- p.104

Many real life problems can naturally be modeled as constraint satisfaction problems (CSPs), which can sometimes contain both variable symmetries and value symmetries. Tree search based CSP solving algorithms often suffer from symmetries, which creates symmetrically equivalent states in the search tree. Exploring more than one of the symmetrically equivalent states is a waste of search efforts. Adding symmetry breaking constraints to a CSP can force the search to visit only one of the symmetrical regions and helps reduce search space. While variable symmetry breaking constraints can be expressed relatively easily and executed efficiently by enforcing lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this thesis, we propose two methods of using symmetry breaking constraints to tackle value symmetries. In the first method, we show theoretically when value symmetries in one CSP model correspond to variable symmetries in another CSP model of the same problem. We also show when variable symmetry breaking constraints in the two models, combined using channeling constraints, are consistent. Such results allow tackling value symmetries efficiently using additional CSP variables and channeling constraints. In the second method, we identify a common and important class of value symmetries, namely symmetries of indistinguishable values, and introduce value precedence to break such symmetries. Although value precedence can be expressed straightforwardly using if-then constraints in existing constraint programming systems, the resulting formulation is inefficient both in terms of size and runtime. We present two propagation algorithms for implementing global constraints on value precedence for integer and set variables respectively. We also characterize the propagation levels attained by various usages of the global constraints and the conditions when the constraints are consistent with variable symmetry breaking constraints. Extensive experiments are conducted to verify the feasibility and efficiency of our two proposals. / Law Yat Chiu. / "September 2005." / Adviser: Jimmy Ho Man Lee. / Source: Dissertation Abstracts International, Volume: 67-07, Section: B, page: 3905. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (p. 112-123). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2003. / Includes bibliographical references (leaves 104-112). Also available in electronic version. Access restricted to campus users.