60 research outputs found
Context-Free Graph Properties via Definable Decompositions
No full textMonadic-second order logic (MSO-logic) is successfully applied in both language theory and algorithm design. In the former, properties definable by MSO-formulas are exactly the regular properties on many structures like, most prominently, strings. In the latter, solving a problem for structures of bounded tree width is routinely done by defining it in terms of an MSO-formula and applying general formula-evaluation procedures like Courcelle's. The present paper furthers the study of second-order logics with close connections to language theory and algorithm design beyond MSO-logic.
We introduce a logic that allows to expand a given structure with an existentially quantified tree decomposition of bounded width and test an MSO-definable property for the resulting expanded structure. It is proposed as a candidate for capturing the notion of "context-free graph properties" since it corresponds to the context-free languages on strings, has the same closure properties, and an alternative definition similar to the one of Chomsky and Schützenberger for context-free languages. Besides studying its language-theoretic aspects, we consider its expressive power as well as the algorithmics of its satisfiability and evaluation problems
Canonizing Graphs of Bounded Tree Width in Logspace
No full textGraph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized in deterministic logarithmic space (logspace). This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous classes of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined
Parameterized Complexity of Fixed-Variable Logics
No full textWe study the complexity of model checking formulas in first-order logic parameterized by the number of distinct variables in the formula. This problem, which is not known to be fixed-parameter tractable, resisted to be properly classified in the context of parameterized complexity. We show that it is complete for a newly-defined complexity class that we propose as an analog of the classical class PSPACE in parameterized complexity. We support this intuition by the following findings: First, the proposed class admits a definition in terms of alternating Turing machines in a similar way as PSPACE can be defined in terms of polynomial-time alternating machines. Second, we show that parameterized versions of other PSPACE-complete problems, like winning certain pebble games and finding restricted resolution refutations, are complete for this class
Platz- und Schaltkreiskomplexität von MSO-beschreibbaren Problemen auf baumartig zerlegbaren Strukturen
No full textDieser Beitrag ist eine deutschsprachige Kurzfassung der Dissertation von Michael Elberfeld [Elb12]. Die Dissertation entwickelt und bearbeitet Fragestellungen aus den Bereichen der Theoretischen Informatik und Mathematischen Logik. Sie untersucht die Platz-, Schaltkreis- und Beschreibungskomplexität von Problemen, die sich durch Formeln in monadischer Logik zweiter Stufe beschreiben lassen und deren Eingaben eine beschränkte Baumweite oder -tiefe besitzen. Die gewonnenen Resultate werden angewendet, um die Komplexität konkreter Entscheidungs-, Zähl- und Optimierungsprobleme aus verschiedenen Anwendungsgebieten zu klassifizieren
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
No full textAn algorithmic meta theorem for a logic and a class C of structures
states that all problems expressible in this logic can be solved
efficiently for inputs from . The prime example is Courcelle's
Theorem, which states that monadic second-order (MSO) definable
problems are linear-time solvable on graphs of bounded tree width. We
contribute new algorithmic meta theorems, which state that
MSO-definable problems are (a) solvable by uniform constant-depth
circuit families (AC0 for decision problems and TC0 for counting
problems) when restricted to input structures of bounded tree depth
and (b) solvable by uniform logarithmic-depth circuit families (NC1
for decision problems and #NC1 for counting problems) when a tree
decomposition of bounded width in term representation is part of the
input. Applications of our theorems include a TC0-completeness proof
for the unary version of integer linear programming with a fixed
number of equations and extensions of a recent result that counting
the number of accepting paths of a visible pushdown automaton lies in
#NC1. Our main technical contributions are a new tree automata model
for unordered, unranked, labeled trees; a method for representing the
tree automata's computations algebraically using convolution circuits;
and a lemma on computing balanced width-3 tree decompositions of trees
in TC0, which encapsulates most of the technical difficulties
surrounding earlier results connecting tree automata and NC1
Stadt-Theater Düsseldorf / Die Meistersinger von Nürnberg : Sonntag, den 14. April 1912, abends 7 Uhr ; Oper in 3 Aufzügen
No full textvon Richard Wagner. Spielleitung: Robert Leffler. Musikalische Leitung: Alfred Fröhlich. Personen: Richard Hedler, Erich Hanfstaengl, Julius Barré, Ernst Bedau, Ernst Winter, Max Otto vom Stadttheater Elberfeld a. G., Willy Placke, Egon Reichenbach, Heinz Leon, Jahn Hofknecht, Karl Deussen, Michael Bohnen, Fritz Bischoff, Eugen Albert, Hermine Fröhlich-Förster, Marie Sieg, Karl Gerick
Space and circuit complexity of monadic second-order definable problemes on tree-decomposable structures
No full textStadt-Theater Düsseldorf / Zapfenstreich : Donnerstag, den 1. Februar 1906 ; Drama in 4 Akten
No full textvon Franz Adam Beyerlein. Spielleitung: Rob. Schlismann-Brandt. Personen: Michael Isailovits, Hermann Rosenberg, Egon Hedeberg, Rob. Schlismann-Brandt, Hans Hofer, Ernst Herz, Hugo Lazak, Luliane Quadri, Ernst Bedau, Eugen Marlow, Julius Pohl, Hermann Heine, Bernhard Heininger, Jahn Hofknecht, Cornelius Dobski, Robert Weberg, Franz de Paula, von Lauffen: Hugo Denzel vom Stadttheater in Elberfeld (Gastspiel auf Engagement für die nächstjährige Spielzeit)In Fraktu
- …
