Browsing by Subject "Computer circuits"

Sort by: Order: Results:

  • Kontinen, Juha; Müller, Julian-Steffen; Schnoor, Henning; Vollmer, Heribert (Wadern : Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, 2015)
    The famous van Benthem theorem states that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation. In this article we prove an exact analogue of this theorem in the framework ...
  • Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2016)
    A framework is developed that extends Hilbert-style proof systems for propositional and modal logics to comprehend their team-based counterparts. The method is applied to classical propositional logic and the modal logic ...
  • Sano, Katsuhiko; Virtema, Jonni (Wadern : Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, 2015)
    We give sound and complete Hilbert-style axiomatizations for propositional dependence logic (PD), modal dependence logic (MDL), and extended modal dependence logic (EMDL) by extending existing axiomatizations for propositional ...
  • Meier, Arne; Ordyniak, Sebastian; Sridharan, Ramanujan; Schindler, Irena (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized ...
  • Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2018)
    We study modal team logic MTL, the team-semantical extension of classical modal logic closed under Boolean negation. Its fragments, such as modal dependence, independence, and inclusion logic, are well-understood. However, ...
  • Kontinen, Juha; Kuusisto, Antti; Virtema, Jonni (Saarbrücken : Dagstuhl Publishing, 2016)
    We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTIMEcomplete. Furthermore, we show that the ...
  • Durand, Arnaud; Haak, Anselm; Kontinen, Juha; Vollmer, Heribert (Saarbrücken : Dagstuhl Publishing, 2016)
    We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. ...
  • Hella, Lauri; Kuusisto, Antti; Meier, Arne; Virtema, Jonni (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    Propositional and modal inclusion logic are formalisms that belong to the family of logics based on team semantics. This article investigates the model checking and validity problems of these logics. We identify complexity ...
  • Hannula, Miika; Kontinen, Juha; Lück, Martin; Virtema, Jonni (Waterloo, NSW : Open Publishing Association, 2016)
    We study quantified propositional logics from the complexity theoretic point of view. First we introduce alternating dependency quantified boolean formulae (ADQBF) which generalize both quantified and dependency quantified ...
  • Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2018)
    We study the logic FO(∼), the extension of first-order logic with team semantics by unrestricted Boolean negation. It was recently shown to be axiomatizable, but otherwise has not yet received much attention in questions ...
  • Chandoo, Maurice (Saarbrücken : Dagstuhl Publishing, 2016)
    The implicit graph conjecture states that every sufficiently small, hereditary graph class has a labeling scheme with a polynomial-time computable label decoder. We approach this conjecture by investigating classes of label ...
  • Lück, Martin; Meier, Arne; Schindler, Irena (Association for Computing Machinery, 2017)
    We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and ...
  • Schulte, M.; Lörch, N.; Leroux, I.D.; Schmidt, Piet O.; Hammerer, K. (College Park, MD : American Physical Society, 2016)
    Optical clocks based on ensembles of trapped ions promise record frequency accuracy with good short-term stability. Most suitable ion species lack closed transitions, so the clock signal must be read out indirectly by ...
  • Peikert, Tim; Garbe, Heyno; Potthast, S. (Göttingen : Copernicus GmbH, 2016)
    This paper introduces a procedural method based on fuzzy logic to analyze systematic the risk of an electronic system in an intentional electromagnetic environment (IEME). The method analyzes the susceptibility of a complex ...
  • Krebs, Andreas; Meier, Arne; Virtema, Jonni; Zimmermann, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2018)
    We develop team semantics for Linear Temporal Logic (LTL) to express hyperproperties, which have recently been identified as a key concept in the verification of information flow properties. Conceptually, we consider an ...
  • Lück, Martin (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2017)
    Modal Team Logic (MTL) extends Väänänen's Modal Dependence Logic (MDL) by Boolean negation. Its satisfiability problem is decidable, but the exact complexity is not yet understood very well. We investigate a model-theoretical ...