Database manipulations using group theory

Details Database manipulations using group theory Database manipulations using group theory

2004-11-15

2008-10-21

Mofiz, Apu (Department: 2161)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07440942

ABSTRACT:
Data in a database describe an application domain such as a satisfiability problem. The data are represented in a manner that expresses the structure inherent in the data and one such representation uses group theory and represents the data as one or more “augmented clauses,” where each clause has a pair (c, G) including a database element c and a group G of group elements g acting on it. A query is encoded in a group theory representation and is executed on the group theory representation of the data to identify database elements and associated group elements satisfying the query. If desired, the satisfying database elements are converted from the group theory representation to the native representation of the data.

REFERENCES:
patent: 6556978 (2003-04-01), Ginsberg et al.
patent: 6601058 (2003-07-01), Forster et al.
patent: 6886153 (2005-04-01), Bevis
patent: 6912700 (2005-06-01), Franco et al.
patent: 2003/0046061 (2003-03-01), Preston et al.
patent: 2004/0019468 (2004-01-01), De Moura et al.
Aloul, F., Ramani, A., Markov, I., and Sakallah, K., PBS: A Backtrack Search Pseudo-Boolean Solver, Fifth International Symposium on the Theory and Applications of Satisfiability Testing, May 6-9, 2000, pp. 346-353.
Babai, L., Luks, E., and Seress, A., Fast Management Of Permutation Groups I, Siam J. On Computing, 1997, vol. 1, No. 1, pp. 1-33.
Baker, A. B., The Hazards Of Fancy Backtracking, In Proceedings of the Twelfth National Conference on Artificial Intelligence, 1994.
Barth, P., A Davis-Putnam Based Enumeration Algorithm For Linear Pseudo-Boolean Optimization, Technical Report MPI-I-95-2-003, Max Planck Institut fur Informatik, Saarbrucken, Germany, Jan. 1995.
Baumgartner, P., FDPLL—A First-Order Davis-Putnam-Logeman-Loveland Procedure, In D. McAllester, editor, CADE-17 The 17th International Conference on Automated Deduction, vol. 1831, pp. 200-219. Springer, 2000.
Baumgartner, P. and Massacci, F., The Taming of the (X)OR, In J. Lloyd, V. Dahl, U. Furbach, M. Kerber, K.-K. Lau, C. Palamidessi, L. M. Pereira, Y. Sagiv, and P. J. Stuckey, editors, Computational Logic—CL 2000, vol. 1861, pp. 508-522. Springer, 2000.
Bayardo, R. J. and Miranker, D. P., A Complexity Analysis Of Space-Bounded Learning Algorithms For The Constraint Satisfaction Problem, In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pp. 298-304, 1996.
Bayardo, R. J. and Schrag, R. C., Using CSP Look-Back Techniques To Solve Real-World SAT Instances, In Proceedings of the Fourteenth National Conference on Artificial Intelligence, pp. 203-208, 1997.
Beame, P. and Pitassi, T., Propositional Proof Complexity: Past, Present And Future, In G. Paun, G. Rozenberg, and A. Salomaa, editors, Current Trends in Theoretical Computer Science, Entering the 21th Century, pp. 42-70. World Scientific, 2001.
Biere, A., Clarke, E., Raimi, R., and Zhu, Y., Verifying Safety Properties Of A PowerPC Microprocessor Using Symbolic Model Checking Without BDDs, Lecture Notes in Computer Science, 1633, 1999.
Bonet, M. L., Pitassi, T., and Raz, R., Lower Bounds For Cutting Planes Proofs With Small Coefficients, Journal of Symbolic Logic, 62(3):708-728, 1997.
Bryant, R. E., Graph-Based Algorithms For Boolean Function Manipulation, IEEE Trans. Comput., C-35(8):677-691, Aug. 1986.
Bryant, R. E., Symbolic Boolean Manipulation With Ordered Binary-Decision Diagrams, ACM Computing Surveys, 24(3):293-318, Jun. 1992.
Buchberger, B., Ein Algorithms Zum Auffinden Der Basiselemente Des Restklassenringes Nach Einum Nulldimensionalen Polynomideal, PhD thesis, University of Innsbruck, Innsbruck, 1965.
Cadoli, M., Schaerf, M., Giovanardi, A., and Giovanardi, M., An Algorithm To Evaluate Quantified Boolean Formulae And Its Experimental Evaluation, Journal of Automated Reasoning, 28(2):101-142, 2002.
Chai, D. and Kuehlmann, A., A Fast Pseudo-Boolean Constraint Solver, In Proceedings of the 40th Design Automation Conference, pp. 830-835, 2003.
Clegg, M., Edmonds, J., and Impagliazzo, R., Using The Groebner Basis Algorithm To Find Proofs Of Unsatisfiability, In Proceedings of the Twenty-Eighth Annual ACM Symp. on Theory of Computing, pp. 174-183, 1996.
Coarfa, C., Demopoulos, D. D., San Miguel Aguirre, A., Subramanian, D. and Vardi, M., Random 3-SAT: The Plot Thickens, In Proceedings of the International Conference on Constraint Programming, 2000.
Cook, S. A., The Complexity Of Theorem-Proving Procedures, In Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing, pp. 151-158, 1971.
Copty, F., Fix, L., Fraer, R., Giunchiglia, E., Kamhi, G., Tacchella, A., and Vardi, M., Benefits Of Bounded Model Checking In An Industrial Setting, In 13th Conference on Computer Aided Verification, CAV'01, Paris, France, Jul. 2001.
Crawford, J. M., A Theoretical Analysis Of Reasoning By Symmetry In First-Order Logic, (Extended Abstract), In AAAI Workshop on Tractable Reasoning, 1992.
Crawford, J. M. and Auton, L. D., Experimental Results On The Crossover Point In Random 3SAT , Artificial Intelligence, 81:31-57, 1996.
Crawford, J. M., Ginsberg, M. L., Luks, E., and Roy, A., Symmetry Breaking Predicates For Search Problems, In Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning, Boston, MA, 1996.
Dixon, H. E. and Ginsberg, M. L., Combining Satisfiability Techniques From AI And OR, Knowledge Engrg. Rev., 15:31-45, 2000.
Dixon, H., Ginsberg, M., and Parkes, A., Generalizing Boolean Satisfiability I: Background and Survey of Existing Work, Journal of Artificial Intelligence Research 21 (Feb. 2004) 193-243.
Dixon, H. E. and Ginsberg, M. L., Inference Methods For A Pseudo-Boolean Satisfiability Solver, In Proceedings of the Eighteenth National Conference on Artificial Intelligence, 2002.
Dubois, O. and Dequen, G., A Backbone-Search Heuristic For Efficient Solving Of Hard 3-SAT Formulae, In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pp. 248-253, 2001.
East, D. and Truszczynski, M., Propositional Satisfiability In Answer-Set Programming, Lecture Notes in Computer Science, 2174, 2001.
East, D. and Truszczynski, M., Propositional Satisfiability In Declarative Programming, Extended version of papers that appeared in Proceedings of AAA1-2000, and Proceedings of K1-2001. http://xxx.lanl.gov/abs/cs.LO/0211033, Nov. 2002.
Freeman, J. W., Improvements To Propositional Satisfiability Search Algorithms, PhD thesis, University of Pennsylvania, PA, 1995.
Frost, D. and Dechter, R., Dead-End Driven Learning, In Proceedings of the Twelfth National Conference on Artificial Intelligence, pp. 294-300, 1994.
GAP, GAP—Groups, Algorithms and Programming, The GAP Group, 2003, http://www-gap.dcs.st-and.ac.uk/gap.
Gelfond, M. and Lifschitz, V., The Stable Model Semantics For Logic Programming, In Proceedings of the 5th International Conference on Logic Programming, pp. 1070-1080. MIT Press, 1988.
Ginsberg, M. L., Dynamic Backtracking, Journal of Artificial Intelligence Research, 1:25-46, 1993.
Ginsberg, M. L. and Geddis, D. F., Is There Any Need For Domain-Dependent Control Information? In Proceedings of the Ninth National Conference on Artificial Intelligence, 1991.
Ginsberg, M. L. and Parkes, A. J., Search, Subsearch and QPROP, In Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning, Breckenridge, Colorado, 2000.
Goldberg, E. and Novikov, Y., BerkMin: A Fast And Robust SAT Solver, In Design Automation and Test in Europe (DATE), pp. 142-149, 2002.
Guignard, M. and Spielberg, K., Logical Reduction Methods In Zero-One Programming, Operations Research, 29, 1981.
Haken, A., Counting Bottlenecks To Show Monotone P ≠NP, In Proceedings 36th Annual IEEE Symp. on Foundations of Computer Science (FOCS-95), pp. 38-40, Milwaukee, MN, 1995. IEEE.
Harrision, M. A., Introduction To Switching And Automata Theory, McGraw-Hill, 1989.
Hooker, J. N. and Vinay, V., Branching Rules For Satisfiability, J. Automated Reasoning, 15:359-383, 1995.
Joslin, D. and Roy, A., Exploiting Symmetry In Lifted

Affiliated with

Also associated with

Rating

Database manipulations using group theory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Database manipulations using group theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database manipulations using group theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4012621