Fundamenta Informaticae - Volume 98, issue 4

Article Type: Research Article

DOI: 10.3233/FI-2010-230

Citation: Fundamenta Informaticae, vol. 98, no. 4, pp. i-i, 2010

Authors: Bojańczyk, Mikołaj | Niwiński, Damian | Rabinovich, Alexander | Radziwończyk-Syta, Adam | Skrzypczak, Michał

Article Type: Research Article

Abstract: An infinite binaryword can be identified with a branch in the full binary tree. We consider sets of branches definable in monadic second-order logic over the tree, where we allow some extra monadic predicates on the nodes. We show that this class equals to the Boolean combinations of sets in the Borel class Σ^0_2 over the Cantor discontinuum. Note that the last coincides with the Borel complexity of ω-regular languages.

Keywords: Monadic 2nd-order logic, infinite words, trees, Borel hierarchy, automata

DOI: 10.3233/FI-2010-231

Citation: Fundamenta Informaticae, vol. 98, no. 4, pp. 337-349, 2010

Authors: Dawar, Anuj | Grädel, Erich

Article Type: Research Article

Abstract: We study 0-1 laws for extensions of first-order logic by Lindström quantifiers. We state sufficient conditions on a quantifier Q expressing a graph property, for the logic FO[Q] – the extension of first-order logic by means of the quantifier Q – to have a 0-1 law. We use these conditions to show, in particular, that FO[Rig], where Rig is the quantifier expressing rigidity, has a 0-1 law. We also show that extensions of first-order logic with …quantifiers for Hamiltonicity, regularity and self-complementarity of graphs do not have a 0-1 law. Blass and Harary pose the question whether there is a logic which is powerful enough to express Hamiltonicity or rigidity and which has a 0-1 law. It is a consequence of our results that there is no such regular logic (in the sense of abstract model theory) in the case of Hamiltonicity, but there is one in the case of rigidity. We also consider sequences of vectorized quantifiers, and show that the extensions of first-order logic obtained by adding such sequences generated by quantifiers that are closed under substructures have 0-1 laws. The positive results also extend to the infinitary logic with finitely many variables. Show more

DOI: 10.3233/FI-2010-232

Citation: Fundamenta Informaticae, vol. 98, no. 4, pp. 351-372, 2010

Authors: Hoffmann, Christian

Article Type: Research Article

Abstract: We consider a graph polynomial ξ (G; x, y, z) introduced by Ilia Averbouch,BennyGodlin, and Johann A.Makowsky (2008). This graph polynomial simultaneously generalizes the Tutte polynomial as well as a bivariate chromatic polynomial defined by Klaus Dohmen, André Pönitz, and Peter Tittmann (2003). We derive an identity which relates the graph polynomial ξ of a thickened graph (i.e. a graph with each edge replaced by k copies of it) to ξ of the original graph. As …a consequence, we observe that at every point (x, y, z), except for points lying within some set of dimension 2, evaluating ξ is #P-hard. Thus, ξ supports Johann A. Makowsky's difficult point conjecture for graph polynomials (2008). Show more

DOI: 10.3233/FI-2010-233

Citation: Fundamenta Informaticae, vol. 98, no. 4, pp. 373-378, 2010

Authors: Kaminski, Michael | Tan, Tony

Article Type: Research Article

Abstract: It is shown that the emptiness problemfor two-pebble automata languages is undecidable and that two-pebble automata are weaker than three-pebble automata.

Keywords: pebble automata, infinite alphabet, undecidability, Hilbert's tenth problem

DOI: 10.3233/FI-2010-234

Citation: Fundamenta Informaticae, vol. 98, no. 4, pp. 379-390, 2010

Authors: Meer, Klaus

Article Type: Research Article

Abstract: 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. Show more

Keywords: Tree-width, Real Number Computations, Descriptive Complexity, Valiant's Model, Dedicated to Johann A. Makowsky on the occasion of his 60th birthday

DOI: 10.3233/FI-2010-235

Citation: Fundamenta Informaticae, vol. 98, no. 4, pp. 391-409, 2010