Tomás Feder
Moshe Y. Vardi
- 1.M. Aschbacher, personal communication.Google Scholar
- 2.F. Afrati and S. S. Cosmadakis, "Expressiveness of restricted recursive queries," Proc. 21st ACM Syrup. on Theory of Computing (1989), 113-126. Google ScholarDigital Library
- 3.F. Afrati, S. S. Cosmadakis, and M. Yannakakis, "On Datalog vs. polynomial time," Proc. 10th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (1991), 13-25. Google ScholarDigital Library
- 4.L. Bahai, "Monte Carlo algorithms in graph isomorphism testing," (1979).Google Scholar
- 5.J. Bang-Jensen and P. Hell, "The effect of two cycles on the complexity of colourings by directed graphs," Discrete Applied Math 26 (1990), 1-23. Google ScholarDigital Library
- 6.R. Dechter, "Constraint networks," In Encyclopedia of Artificial Intelligence, 1992, 276- 285.Google Scholar
- 7.P. Erd6s, "Graph theory and probability," Canadian J. of Math. 11 (1959), 34-38.Google ScholarCross Ref
- 8.R. Fagin, "Generalized first-order spectra, and polynomial-time recognizable sets," in R. Karp (ed.), Complexity of Computations, AMS, 1974.Google Scholar
- 9.T. Feder, "Stable Networks and Product Graphs," doctorM dissertation, Stanford University ( 1991). Google ScholarDigital Library
- 10.T. Feder, "Removing inequalities and negation for homomorphism-closed problems," in preparation.Google Scholar
- 11.M. Furst, J. E. Hopcroft, and E. Luks, "Polynomial-time algorithms for permutation groups," Proc. 21st IEEE Symp. on Found. of Comp. Sci. (1980), 36-41.Google ScholarDigital Library
- 12.D. M. Goldschmidt, "2-fusion in finite groups," Annals of Math. 99 (1974), 70-117.Google ScholarCross Ref
- 13.P. Hell and J. Ne#etfil, "On the complexity of H-coloring," J. Comb. Theory, Series B 48 (1990), 92-110. Google ScholarDigital Library
- 14.G. G. Hillebrand, P. C. Kanellakis, H. G. Mairson, and M. Y. Vardi, "Tools for Datalog boundedness," Proc. 10th ACM SIGACT- SIGMOD-SIGART Symp. on Principles of Database Systems (1991), 1-12. Google ScholarDigital Library
- 15.C. M. Hoffmann, "Group-Theoretic Algorithms and Graph Isomorphism," Lecture Notes in Comp. Sci. 136 (1982), Springer- Verlag.Google Scholar
- 16.P. G. Kolaitis and M. Y. Vardi, "The decision problem for the probabilities of higher-order properties," Proc. 19th ACM Syrup. on Theory of Computing (1987), 425-435. Google ScholarDigital Library
- 17.P. G. Kolaitis and M. Y. Vardi, "On the expressive power of Datalog: tools and a case study," Proc. 9th ACM SIGACT-SIGMOD- SIGART Symp. on Principles of Database Systems (1990), 61-71. Google ScholarDigital Library
- 18.V.Kumar, "Algorithms for constraint-satisfaction problems," AI Magazine 13 (1992), 32-44. Google ScholarDigital Library
- 19.R. E. Ladner, "On the structure of polynomial time reducibility," J. Assoc. Comput. Mach. 22 (1975), 155-171. Google ScholarDigital Library
- 20.V. S. Lakshmanan and A. O. Mendelzon, "Inductive pebble games and the expressive power of Datalog," Proc. 8th ACM SIGACT- SIGMOD-SIGART Symp. on Principles of Database Systems (1989), 301-310. Google ScholarDigital Library
- 21.A. Lubiw, "Some NP-complete problems similar to graph isomorphism," SIAM J. Comput. 10 (1981), 11-21.Google ScholarDigital Library
- 22.P. Meseguer, "Constraint satisfaction problem: an overview," AICOM 2 (1989), 3-16.Google ScholarDigital Library
- 23.E. Mayr and A. Subramanian, "The complexity of circuit value and network stability," J. Comput. Syst. Sci. 44 (1992), 302-323. Google ScholarDigital Library
- 24.C. H. Papadimitriou and M. Yannakakis, "Optimization, approximation, and complexity classes," J. Comput. Syst. Sci. 43 (1991), 425- 440.Google ScholarCross Ref
- 25.A. A. Razborov, "Lower bounds on monotone complexity of the logical permanent," Math. Notes of the Academy of Sciences of the USSR 37 (1985), 485-493.Google ScholarCross Ref
- 26.T. J. Schaefer, "The complexity of satisfiability problems," Proe. 10th ACM Symp. on Theory of Computing (1978), 216-226. Google ScholarDigital Library
- 27.Ullman, J.D.: Principles of Database and Knowledge-Base Systems, Vol I. Computer Science Press, 1989. Google ScholarDigital Library
Index Terms
- Monotone monadic SNP and constraint satisfaction
Recommendations
A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is ...
Periodic Constraint Satisfaction Problems: Tractable Subclasses
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem . An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly ...
Comments