Tree-width in Algebraic Complexity

• Autorzy: Meer K.
• Języki publikacji: EN

Abstrakty

EN

The paper surveys some of the author's work studying the algorithmic importance of the tree-width notion in algebraic frameworks. Two approaches are described. The first gives an algorithmicmeta-theoremfor certain logically characterized propertieswithin the Blum-Shub-Smale BSS model of computation over the reals. The second reports on recent joint work with P. Koiran relating Boolean complexity and Valiant’s approach to study families of polynomial systems over infinite fields and their complexity. We define particular families of polynomials via bounding the tree-width of suitably attached graphs and study the expressive power of the resulting families. The work described here is partially co-authoredwith and partially verymuch influenced by previous work of Janos A. Makowsky.

Słowa kluczowe

EN

tree-width; real number computations; Descriptive Complexity; Valiant's model

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 98, nr 4
• Strony: 391--409
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Meer K.

Bibliografia

• [1] Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs, J. Algorithms, 12(2), 1991, 308-340.
• [2] Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation, Springer-Verlag, New York, 1998.
• [3] Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NPcompleteness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.), 21(1), 1989, 1-46.
• [4] Bürgisser, P., Clausen, M., Shokrollahi, M. A.: Algebraic complexity theory, vol. 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin, 1997, With the collaboration of Thomas Lickteig.
• [5] Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. And Comput., 85(1), 1990, 12-75.
• [6] Courcelle, B.,Makowsky, J. A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33(2), 2000, 125-150.
• [7] Courcelle, B., Makowsky, J. A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Discrete Appl. Math., 108(1-2), 2001, 23-52.
• [8] Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree decomposable graphs, Theoretical Computer Science, 109, 1993, 49-82.
• [9] Cucker, F.,Meer, K.: Logics which capture complexity classes over the reals, J. Symbolic Logic, 64(1), 1999, 363-390.
• [10] Downey, R. G., Fellows, M. R.: Parameterized complexity, Monographs in Computer Science, Springer-Verlag, New York, 1999.
• [11] Ebbinghaus, H.-D., Flum, J.: Finite model theory, Springer Monographs in Mathematics, enlarged edition, Springer, Berlin, 2006.
• [12] Feferman, S., Vaught, R. L.: The first order properties of products of algebraic systems, Fund. Math., 47, 1959, 57-103.
• [13] Ferrara, A., Pan, G., Vardi, M. Y.: Treewidth in Verification: Local vs. Global, in: Logic for Programming, Artificial Intelligence, and Reasoning LPR (Montego Bay, 2005), vol. 3835 of Lecture Notes in Comput. Sci., Springer, 2005, 489-503.
• [14] Fischer, E., Makowsky, J. A., Ravve, E. V.: Counting truth assignments of formulas of bounded tree-width or clique-width, Discrete Appl. Math., 156(4), 2008, 511-529.
• [15] Flarup, U., Koiran, P., Lyaudet, L.: On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices, in: International Symposium on Algorithms and Computation ISAAC (Sendai, 2007), vol. 4835 of Lecture Notes in Comput. Sci., Springer, 2007, 124-136.
• [16] Flarup, U., Lyaudet, L.: On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract), in: Computer Science Symposium in Russia CSR (Moscow, 2008), vol. 5010 of Lect. Notes in Comput. Sci., Springer, 2008, 180-193.
• [17] Flum, J., Grohe, M.: Parameterized complexity theory, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2006.
• [18] Grädel, E., Gurevich, Y.: Metafinite model theory, Inform. and Comput., 140(1), 1998, 26-81.
• [19] Grädel, E.,Meer, K.: Descriptive complexity theory over the real numbers, in: The mathematics of numerical analysis (Park City, UT, 1995), vol. 32 of Lectures in Appl. Math., Amer. Math. Soc., Providence, RI, 1996, 381-403.
• [20] Halin, R.: S-functions for graphs, J. Geometry, 8(1-2), 1976, 171-186.
• [21] Jukna, S.: The effect of null-chains on the complexity of contact schemes, in: Fundamentals of Computation Theory FCT (Szeged, 1989), vol. 380 of Lecture Notes in Comput. Sci., Springer, New York, 1989, 246-256.
• [22] Koiran, P., Meer, K.: On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width, in: Graph-Theoretic Concepts in Computer ScienceWG (Durham, 2008), vol. 5344 of Lecture Notes in Comput. Sci., Springer, 2008, 252-263.
• [23] Krause, M., Meinel, C., Waack, S.: Separating the eraser Turing machine classes Le, NLe, co-NLe and Pe, Theoret. Comput. Sci., 86(2), 1991, 267-275.
• [24] Makowsky, J. A.: Algorithmic uses of the Feferman-Vaught theorem, Ann. Pure Appl. Logic, 126(1-3), 2004, 159-213.
• [25] Makowsky, J. A.: From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials, in: Computability in Europe: Logical Approaches to Computational Barriers CiE (Swansea, 2006), vol. 3988 of Lecture Notes in Computer Science, Springer, 2006, 330-341.
• [26] Makowsky, J. A., Meer, K.: Polynomials of bounded tree-width, in: Foundations of computational mathematics (Hong Kong, 2000), Proceedings of the Smalefest 2000, World Sci. Publ., River Edge, NJ, 2002, 211-250.
• [27] Meer, K.: On the complexity of quadratic programming in real number models of computation, Theoret. Comput. Sci., 133(1), 1994, 85-94.
• [28] Niedermeier, R.: Invitation to fixed-parameter algorithms, vol. 31 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2006.
• [29] Robertson, N., Seymour, P. D.: Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7(3), 1986, 309-322.
• [30] Samer, M., Szeider, S.: Algorithms for PropositionalModel Counting, in: Logic for Programming, Artificial Intelligence, and Reasoning LPR (Yerevan, 2007), vol. 4790 of Lecture Notes in Computer Science, Springer, 2007, 484-498.
• [31] Valiant, L. G.: The complexity of computing the permanent, Theoret. Comput. Sci., 8(2), 1979, 189-201.
• [32] Valiant, L. G.: Reducibility by algebraic projections, in: Logic and algorithmic (Zurich, 1980), vol. 30 of Monograph. Enseign. Math., Univ. Gen`eve, Geneva, 1982, 365-380.