Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Constraint database (4)
- Classification (3)
- Evolution (3)
- Interpolation (3)
- Support vector machine (3)
-
- Table segmentation (3)
- Active learning (2)
- Bounded verification (2)
- Cretan Hieroglyph (2)
- Cubic spline (2)
- Data mining (2)
- Datalog (2)
- Decision tree (2)
- Digital libraries (2)
- End user software engineering (2)
- Formal analysis (2)
- Game theory (2)
- Historic documents (2)
- Linear A (2)
- Linear B (2)
- Machine learning (2)
- Neural networks (2)
- Phylogenetic tree (2)
- Protein (2)
- Recurrence equation (2)
- Refactoring (2)
- Reliability (2)
- SVM (2)
- Silent speech recognition (2)
- Speech kinematics (2)
Articles 31 - 60 of 274
Full-Text Articles in Entire DC Network
A Game-Theoretic Analysis Of The Nuclear Non-Proliferation Treaty, Peter Revesz
A Game-Theoretic Analysis Of The Nuclear Non-Proliferation Treaty, Peter Revesz
CSE Conference and Workshop Papers
Although nuclear non-proliferation is an almost universal human desire, in practice, the negotiated treaties appear unable to prevent the steady growth of the number of states that have nuclear weapons. We propose a computational model for understanding the complex issues behind nuclear arms negotiations, the motivations of various states to enter a nuclear weapons program and the ways to diffuse crisis situations.
Estimating The Flight Path Of Moving Objects Based On Acceleration Data, Peter Revesz
Estimating The Flight Path Of Moving Objects Based On Acceleration Data, Peter Revesz
CSE Conference and Workshop Papers
Inertial navigation is the problem of estimating the flight path of a moving object based on only acceleration measurements. This paper describes and compares two approaches for inertial navigation. Both approaches estimate the flight path of the moving object using cubic spline interpolation, but they find the coefficients of the cubic spline pieces by different methods. The first approach uses a tridiagonal matrix, while the second approach uses recurrence equations. They also require different boundary conditions. While both approaches work in O(n) time where n is the number of given acceleration measurements, the recurrence equation-based method can be easier updated …
Cubic Spline Interpolation By Solving A Recurrence Equation Instead Of A Tridiagonal Matrix, Peter Revesz
Cubic Spline Interpolation By Solving A Recurrence Equation Instead Of A Tridiagonal Matrix, Peter Revesz
CSE Conference and Workshop Papers
The cubic spline interpolation method is proba- bly the most widely-used polynomial interpolation method for functions of one variable. However, the cubic spline method requires solving a tridiagonal matrix-vector equation with an O(n) computational time complexity where n is the number of data measurements. Even an O(n) time complexity may be too much in some time-ciritical applications, such as continuously estimating and updating the flight paths of moving objects. This paper shows that under certain boundary conditions the tridiagonal matrix solving step of the cubic spline method could be entirely eliminated and instead the coefficients of the unknown cubic polynomials …
Across-Speaker Articulatory Normalization For Speaker-Independent Silent Speech Recognition, Jun Wang, Ashok Samal, Jordan Green
Across-Speaker Articulatory Normalization For Speaker-Independent Silent Speech Recognition, Jun Wang, Ashok Samal, Jordan Green
CSE Conference and Workshop Papers
Silent speech interfaces (SSIs), which recognize speech from articulatory information (i.e., without using audio information), have the potential to enable persons with laryngectomy or a neurological disease to produce synthesized speech with a natural sounding voice using their tongue and lips. Current approaches to SSIs have largely relied on speaker-dependent recognition models to minimize the negative effects of talker variation on recognition accuracy. Speaker-independent approaches are needed to reduce the large amount of training data required from each user; only limited articulatory samples are often available for persons with moderate to severe speech impairments, due to the logistic difficulty of …
Preliminary Test Of A Real-Time, Interactive Silent Speech Interface Based On Electromagnetic Articulograph, Jun Wang, Ashok Samal, Jordan R. Green
Preliminary Test Of A Real-Time, Interactive Silent Speech Interface Based On Electromagnetic Articulograph, Jun Wang, Ashok Samal, Jordan R. Green
CSE Conference and Workshop Papers
A silent speech interface (SSI) maps articulatory movement data to speech output. Although still in experimental stages, silent speech interfaces hold significant potential for facilitating oral communication in persons after laryngectomy or with other severe voice impairments. Despite the recent efforts on silent speech recognition algorithm development using offline data analysis, online test of SSIs have rarely been conducted. In this paper, we present a preliminary, online test of a real-time, interactive SSI based on electromagnetic motion tracking. The SSI played back synthesized speech sounds in response to the user’s tongue and lip movements. Three English talkers participated in this …
Variable Bounds Analysis Of A Climate Model Using Software Verification Techniques, Peter Revesz, Robert Woodward
Variable Bounds Analysis Of A Climate Model Using Software Verification Techniques, Peter Revesz, Robert Woodward
CSE Conference and Workshop Papers
Software verification techniques often use some approximation method that identifies the limits of the possible range of values that variables in a computer program can take during execution. Current climate models are complex computer programs that are typically iterated time-step by time-step to predict the next value of the climate-related variables. Because these iterative methods are necessarily computed only for a fixed number of iterations, they are unable to answer many long-range questions that may be posed regarding climate change, for example, whether there are natural fluctuations or whether a tipping point is reached after which there is no return …
Yeast Pheromone Pathway Modeling Using Petri Nets, Stephen D. Scott, Abhishek Majumdar, Jitender S. Deogun, Steven D. Harris
Yeast Pheromone Pathway Modeling Using Petri Nets, Stephen D. Scott, Abhishek Majumdar, Jitender S. Deogun, Steven D. Harris
CSE Conference and Workshop Papers
Background: Our environment is composed of biological components of varying magnitude. The relationships between the different biological elements can be represented as a biological network. The process of mating in S. cerevisiae is initiated by secretion of pheromone by one of the cells. Our interest lies in one particular question: how does a cell dynamically adapt the pathway to continue mating under severe environmental changes or under mutation (which might result in the loss of functionality of some proteins known to participate in the pheromone pathway). Our work attempts to answer this question. To achieve this, we first propose a …
A Comparison Of A Campus Cluster And Open Science Grid Platforms For Protein- Guided Assembly Using Pegasus Workflow Management System, Natasha Pavlovikj, Kevin Begcy, Sairam Behera, Malachy Campbell, Harkamal Walia, Jitender S. Deogun
A Comparison Of A Campus Cluster And Open Science Grid Platforms For Protein- Guided Assembly Using Pegasus Workflow Management System, Natasha Pavlovikj, Kevin Begcy, Sairam Behera, Malachy Campbell, Harkamal Walia, Jitender S. Deogun
CSE Conference and Workshop Papers
Scientific workflows are a useful tool for managing large and complex computational tasks. Due to its intensive resource requirements, the scientific workflows are often executed on distributed platforms, including campus clusters, grids and clouds. In this paper we build a scientific workflow for blast2cap3, the protein-guided assembly, using the Pegasus Workflow Management System (Pegasus WMS). The modularity of blast2cap3 allows us to decompose the existing serial approach on multiple tasks, some of which can be run in parallel. Afterwards, this workflow is deployed on two distributed execution platforms: Sandhills, the University of Nebraska Campus Cluster, and the Open Science …
Transforming Web Tables To A Relational Database, David W. Embley, George Nagy, Sharad C. Seth
Transforming Web Tables To A Relational Database, David W. Embley, George Nagy, Sharad C. Seth
CSE Conference and Workshop Papers
HTML tables represent a significant fraction of web data. The often complex headers of such tables are determined accurately using their indexing property. Isolated headers are factored to extract category hierarchies. Web tables are then transformed into a canonical form and imported into a relational database. The proposed processing allows for the formulation of arbitrary SQL queries over the collection of induced relational tables.
Word Recognition From Continuous Articulatory Movement Time-Series Data Using Symbolic Representations, Jun Wang, Arvind Balasubramanian, Luis Mojica De La Vega, Jordan R. Green, Ashok Samal, Balakrishnan Prabhakaran
Word Recognition From Continuous Articulatory Movement Time-Series Data Using Symbolic Representations, Jun Wang, Arvind Balasubramanian, Luis Mojica De La Vega, Jordan R. Green, Ashok Samal, Balakrishnan Prabhakaran
CSE Conference and Workshop Papers
Although still in experimental stage, articulation-based silent speech interfaces may have significant potential for facilitating oral communication in persons with voice and speech problems. An articulation-based silent speech interface converts articulatory movement information to audible words. The complexity of speech production mechanism (e.g., co-articulation) makes the conversion a formidable problem. In this paper, we reported a novel, real-time algorithm for recognizing words from continuous articulatory movements. This approach differed from prior work in that (1) it focused on word-level, rather than phoneme-level; (2) online segmentation and recognition were conducted at the same time; and (3) a symbolic representation (SAX) was …
Segmenting Tables Via Indexing Of Value Cells By Table Headers, Sharad C. Seth, George Nagy
Segmenting Tables Via Indexing Of Value Cells By Table Headers, Sharad C. Seth, George Nagy
CSE Conference and Workshop Papers
Correct segmentation of a web table into its component regions is the essential first step to understanding tabular data. Our algorithmic solution to the segmentation problem relies on the property that strings defining row and column header paths uniquely index each data cell in the table. We segment the table using only “logical layout analysis” without resorting to any appearance features or natural language understanding. We start with a CSV table that preserves the 2- dimensional structure and contents of the original source table (e.g., an HTML table) but not font size, font weight, and color. The indexing property of …
Human Performance Regression Testing, Amanda Swearngin, Myra B. Cohen, Bonnie E. John, Rachel K. E. Bellamy
Human Performance Regression Testing, Amanda Swearngin, Myra B. Cohen, Bonnie E. John, Rachel K. E. Bellamy
CSE Conference and Workshop Papers
As software systems evolve, new interface features such as keyboard shortcuts and toolbars are introduced. While it is common to regression test the new features for functional correctness, there has been less focus on systematic regression testing for usability, due to the effort and time involved in human studies. Cognitive modeling tools such as CogTool provide some help by computing predictions of user performance, but they still require manual effort to describe the user interface and tasks, limiting regression testing efforts. In recent work, we developed CogTool-Helper to reduce the effort required to generate human performance models of existing systems. …
Data Mining Of Pancreatic Cancer Protein Databases, Peter Revesz, Christopher Assi
Data Mining Of Pancreatic Cancer Protein Databases, Peter Revesz, Christopher Assi
CSE Conference and Workshop Papers
Data mining of protein databases poses special challenges because many protein databases are non- relational whereas most data mining and machine learning algorithms assume the input data to be a type of rela- tional database that is also representable as an ARFF file. We developed a method to restructure protein databases so that they become amenable for various data mining and machine learning tools. Our restructuring method en- abled us to apply both decision tree and support vector machine classifiers to a pancreatic protein database. The SVM classifier that used both GO term and PFAM families to characterize proteins gave …
Hog: Distributed Hadoop Mapreduce On The Grid, Chen He, Derek J. Weitzel, David Swanson, Ying Lu
Hog: Distributed Hadoop Mapreduce On The Grid, Chen He, Derek J. Weitzel, David Swanson, Ying Lu
CSE Conference and Workshop Papers
MapReduce is a powerful data processing platform for commercial and academic applications. In this paper, we build a novel Hadoop MapReduce framework executed on the Open Science Grid which spans multiple institutions across the United States – Hadoop On the Grid (HOG). It is different from previous MapReduce platforms that run on dedicated environments like clusters or clouds. HOG provides a free, elastic, and dynamic MapReduce environment on the opportunistic resources of the grid. In HOG, we improve Hadoop’s fault tolerance for wide area data analysis by mapping data centers across the U.S. to virtual racks and creating multi-institution failure …
Temporal Data Mining Of Uncertain Water Reservoir Data, Abhinaya Mohan, Peter Revesz
Temporal Data Mining Of Uncertain Water Reservoir Data, Abhinaya Mohan, Peter Revesz
CSE Conference and Workshop Papers
This paper describes the challenges of data mining uncertain water reservoir data based on past human operations in order to learn from them reservoir policies that can be automated for the future operation of the water reservoirs. Records of human operations of water reservoirs often contain uncertain data. For example, the recorded amounts of water released and retained in the water reservoirs are typically uncertain, i.e., they are bounded by some minimum and maximum values. Moreover, the time of release is also uncertain, i.e., typically only monthly or weekly amounts are recorded. To increase the effectiveness of data mining of …
Resonant Wireless Power Transfer To Ground Sensors From A Uav, Brent Griffin, Carrick Detweiler
Resonant Wireless Power Transfer To Ground Sensors From A Uav, Brent Griffin, Carrick Detweiler
CSE Conference and Workshop Papers
Wireless magnetic resonant power transfer is an emerging technology that has many advantages over other wireless power transfer methods due to its safety, lack of interference, and efficiency at medium ranges. In this paper, we develop a wireless magnetic resonant power transfer system that enables unmanned aerial vehicles (UAVs) to provide power to, and recharge batteries of wireless sensors and other electronics far removed from the electric grid. We address the difficulties of implementing and outfitting this system on a UAV with limited payload capabilities and develop a controller that maximizes the received power as the UAV moves into and …
Adaptive Energy-Efficient Task Partitioning For Heterogeneous Multi-Core Multiprocessor Real-Time Systems, Shivashis Saha, Jitender S. Deogun, Ying Lu
Adaptive Energy-Efficient Task Partitioning For Heterogeneous Multi-Core Multiprocessor Real-Time Systems, Shivashis Saha, Jitender S. Deogun, Ying Lu
CSE Conference and Workshop Papers
The designs of heterogeneous multi-core multiprocessor real-time systems are evolving for higher energy efficiency at the cost of increased heat density. This adversely effects the reliability and performance of the real-time systems. Moreover, the partitioning of periodic real-time tasks based on their worst case execution time can lead to significant energy wastage.
In this paper, we investigate adaptive energy-efficient task partitioning for heterogeneous multi-core multiprocessor realtime systems. We use a power model which incorporates the impact of temperature and voltage of a processor on its static power consumption. Two different thermal models are used to estimate the peak temperature of …
Hyscaleii: A High Performance Hybrid Optical Network Architecture For Data Centers, Shivashis Saha, Jitender S. Deogun, Lisong Xu
Hyscaleii: A High Performance Hybrid Optical Network Architecture For Data Centers, Shivashis Saha, Jitender S. Deogun, Lisong Xu
CSE Conference and Workshop Papers
Tremendous growth in data-intensive cloud applications have resulted in an increased demand for highly scalable data center network (DCN) architectures with high throughput and low network complexity. In this paper, we propose HyScaleII to improve the performance of HyScale [17]. HyScaleII is a switchcentric high performance hybrid optical network based DCN architecture that has most of the desirable properties of a data center, e.g. high scalability, low diameter, high bisection width, fault-tolerance, and low network complexity. We also present an efficient and simple routing scheme called HySII routing, which exploits the structural properties of HyScaleII. In our experiments, HyScaleII …
Connecting Soil To The Cloud: A Wireless Underground Sensor Network Testbed, John Tooker, Xin Dong, Mehmet C. Vuran, Suat Irmak
Connecting Soil To The Cloud: A Wireless Underground Sensor Network Testbed, John Tooker, Xin Dong, Mehmet C. Vuran, Suat Irmak
CSE Conference and Workshop Papers
In this demo, a novel underground communication system and an online underground sensor network testbed is demonstrated. The underground communication system, developed in the Cyber-physical Networking (CPN) Laboratory at the University of Nebraska-Lincoln, includes an underground antenna that is tailored to mitigate the adverse effects of soil on underground communication. An online connection is established with the CPN underground sensor network testbed that is located at Clay Center, Nebraska. The underground sensor network testbed consists of a network of underground communication systems equipped with soil moisture sensors and a mobile data harvesting unit equipped with cellular communication capabilities. Real-time soil …
An Efficient Water-Filling Algorithm For Power Allocation In Ofdm-Based Cognitive Radio Systems, Qilin Qi, Yaoqing Lamar Yang
An Efficient Water-Filling Algorithm For Power Allocation In Ofdm-Based Cognitive Radio Systems, Qilin Qi, Yaoqing Lamar Yang
CSE Conference and Workshop Papers
In this paper, we present a new water-filling algorithm for power allocation in Orthogonal Frequency Division Multiplexing (OFDM) – based cognitive radio systems. The conventional water-filling algorithm cannot be directly employed for power allocation in a cognitive radio system, because there are more power constraints in the cognitive radio power allocation problem than in the classic OFDM system. In this paper, a novel algorithm based on iterative water-filling is presented to overcome such limitations. However, the computational complexity in iterative water-filling is very high. Thus, we explore features of the water-filling algorithm and propose a low-complexity algorithm using power-increment or …
Sensing Through The Continent: Towards Monitoring Migratory Birds Using Cellular Sensor Networks, David Anthony, William P. Bennett, Mehmet C. Vuran, Matthew B. Dwyer, Sebastian Elbaum, Anne Lacy, Mike Engels, Walter Wehtje
Sensing Through The Continent: Towards Monitoring Migratory Birds Using Cellular Sensor Networks, David Anthony, William P. Bennett, Mehmet C. Vuran, Matthew B. Dwyer, Sebastian Elbaum, Anne Lacy, Mike Engels, Walter Wehtje
CSE Conference and Workshop Papers
This paper presents CraneTracker, a novel sensor platform for monitoring migratory birds. The platform is designed to monitor Whooping Cranes, an endangered species that conducts an annual migration of 4, 000 km between southern Texas and north-central Canada. CraneTracker includes a rich set of sensors, a multi-modal radio, and power control circuitry for sustainable, continental-scale information delivery during migration. The need for large-scale connectivity motivates the use of cellular technology in low-cost sensor platforms augmented by a low-power transceiver for ad-hoc connectivity. This platform leads to a new class of cellular sensor networks (CSNs) for time-critical and mobile sensing applications. …
A Performance Comparison Of Mobile Wimax Spectrums: 2.5 Ghz Vs. 3.65 Ghz, Pradhumna Shrestha, Michael Hempel, Puttipong Mahasukhon, Tao Ma, Hamid Sharif
A Performance Comparison Of Mobile Wimax Spectrums: 2.5 Ghz Vs. 3.65 Ghz, Pradhumna Shrestha, Michael Hempel, Puttipong Mahasukhon, Tao Ma, Hamid Sharif
CSE Conference and Workshop Papers
Mobile WiMAX is a popular broadband solution with diverse applications. In the United States, the Federal Communications Commission (FCC) currently issues licenses for Mobile WiMAX in several frequency bands, of which 2.5 GHz and 3.65 GHz are the most prevalent. A significant amount of research has been conducted in the domain of 2.5 GHz due to its widespread commercial use. However, no such work – academic or industrial – has been reported for 3.65 GHz, in spite of it being a more favorable option for many applications, particularly because of its licensing requirements. In this paper, we present a comprehensive …
Amplifying Tests To Validate Exception Handling Code, Pingyu Zhang, Sebastian Elbaum
Amplifying Tests To Validate Exception Handling Code, Pingyu Zhang, Sebastian Elbaum
CSE Conference and Workshop Papers
Validating code handling exceptional behavior is difficult, particularly when dealing with external resources that may be noisy and unreliable, as it requires: 1) the systematic exploration of the space of exceptions that may be thrown by the external resources, and 2) the setup of the context to trigger specific patterns of exceptions. In this work we present an approach that addresses those difficulties by performing an exhaustive amplification of the space of exceptional behavior associated with an external resource that is exercised by a test suite. Each amplification attempts to expose a program exception handling construct to new behavior by …
Finding Suitable Programs: Semantic Search With Incomplete And Lightweight Specifications, Kathryn T. Stolee
Finding Suitable Programs: Semantic Search With Incomplete And Lightweight Specifications, Kathryn T. Stolee
CSE Conference and Workshop Papers
Finding suitable code for reuse is a common task for programmers. Two general approaches dominate the code search literature: syntactic and semantic. While queries for syntactic search are easy to compose, the results are often vague or irrelevant. On the other hand, a semantic search may return relevant results, but current techniques require developers to write specifications by hand, are costly as potentially matching code need to be executed to verify congruence with the specifications, or only return exact matches. In this work, we propose an approach for semantic search in which programmers specify lightweight, incomplete specifications and an SMT …
Space-Efficient Algorithms For Reachability In Surface-Embedded Graphs, Derrick Stolee, N. V. Vinodchandran
Space-Efficient Algorithms For Reachability In Surface-Embedded Graphs, Derrick Stolee, N. V. Vinodchandran
CSE Conference and Workshop Papers
This work presents a log-space reduction which compresses an n-vertex directed acyclic graph with m(n) sources embedded on a surface of genus g(n), to a graph with O(m(n) + g(n)) vertices while preserving reachability between a given pair of vertices. Applying existing algorithms to this reduced graph yields new deterministic algorithms with improved space bounds as well as improved simultaneous time space bounds for the reachability problem over a large class of directed acyclic graphs. Specifically, it significantly extends the class of surface-embedded graphs with log-space reachability algorithms: from planar graphs with O(log n) sources, to graphs with …
Mobile Data Harvesting In Wireless Underground Sensor Networks, John Tooker, Mehmet C. Vuran
Mobile Data Harvesting In Wireless Underground Sensor Networks, John Tooker, Mehmet C. Vuran
CSE Conference and Workshop Papers
Wireless Underground Sensor Networks (WUSNs) allow for continuous field monitoring without interfering with aboveground activities, such as plowing or football games. Due to the increased path loss in soil, it is challenging to ensure that a large-scale underground network is connected while still being cost effective in terms of deployment and maintenance.
In this paper, a practical WUSN architecture is developed, consisting of mobile nodes that harvest data from stationary underground nodes. To this end, the impacts of packet size and error control schemes on network performance are investigated through field experiments. By developing a better understanding of the wireless …
Tcp Congestion Avoidance Algorithm Identification (Caai), Peng Yang, Wen Luo, Lisong Xu, Jitender Deogun, Ying Lu
Tcp Congestion Avoidance Algorithm Identification (Caai), Peng Yang, Wen Luo, Lisong Xu, Jitender Deogun, Ying Lu
CSE Conference and Workshop Papers
The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional AIMD algorithm, whereas Internet traffic is now controlled by many different TCP algorithms, such as AIMD, BIC, CUBIC, and CTCP. However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of …
Adaptive Neighborhood Inverse Consistence As Lookahead For Non-Binary Csps, Robert J. Woodward, Shant K. Karakashian, Berthe Y. Choueiry, Christian Bessiere
Adaptive Neighborhood Inverse Consistence As Lookahead For Non-Binary Csps, Robert J. Woodward, Shant K. Karakashian, Berthe Y. Choueiry, Christian Bessiere
CSE Conference and Workshop Papers
Contributions
1.The property Relational Neighborhood Inverse Consistency (RNIC)
2.Characterization of RNIC in relation to previously known properties
3.An efficient algorithm for enforcing RNIC, bounded by degree of the dual graph
4.Three reformulations of the dual graph to address topological limitations of the dual graph
5.An adaptive, automatic selection policy for choosing the appropriate dual graph
6.Empirical evidence on difficult CSP benchmarks
Definition
A Constraint Satisfaction Problem (CSP) is a combinatorial decision problem defined by a set of variables {A,B,C,…}, a set of domain values for these variables, and a set of constraints {R1,R2,R3,…} restricting …
Understanding User Generated Content Characteristics : A Hot-Event Perspective, Miao Wang, Guodong Li, Jie Feng, Lisong Xu, Byrav Ramamurthy, Wei Li, Xiaohong Guan
Understanding User Generated Content Characteristics : A Hot-Event Perspective, Miao Wang, Guodong Li, Jie Feng, Lisong Xu, Byrav Ramamurthy, Wei Li, Xiaohong Guan
CSE Conference and Workshop Papers
Nowadays, millions of Internet users watch and upload a large number of videos on User Generated Content (UGC) sites (e.g., Youtube) everyday. Moreover, online videos about hot events, such as breaking news and Olympic games, attract lots of users. In this paper, we study the characteristics of hot-event videos by collecting video traces of the largest UGC site in China for 28 days. We first empirically study statistical properties of such videos and find that hot-event videos contribute a large number of views, even though the total number of hotevent videos is relatively small. In addition, there exist extremely active …
A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder
A Reformulation Strategy For Multi-Dimensional Csps: The Case Study Of The Set Game, Amanda Swearngin, Berthe Y. Choueiry, Eugene C. Freuder
CSE Conference and Workshop Papers
In this paper we describe a reformulation strategy for solving multi-dimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the uni-dimensional constraints in the problem. It exploits the approximate symmetries identified on the domain values in order to enforce the selected constraint on the simplified problem. This paper uses the game of SET, a combinatorial card game, to motivate and illustrate our strategy. We propose a multi-dimensional constraint model for SET, and describe a basic constraint solver for finding all solutions of an instance of the game. Then, we introduce an algorithm that …