Martin Mundhenk - Publications

  • An AC1-complete model checking problem for intuitionistic logic
    Mundhenk, Weiß. Computational Complexity, 2013 (to appear). [ Preliminary version ]

  • Complexity of model checking for logics over Kripke models
    Müller, Meier, Mundhenk, Vollmer. Bull. EATCS, 2012.

  • The complexity of monotone hybrid logics over linear frames and the natural numbers
    Göller, Meier, Mundhenk, Schneider, Thomas, Weiß. Advances in Modal Logic, 2012.

  • Intuitionistic implication makes model checking hard
    Mundhenk, Weiß. LMCS 8(2:3), 2012.

  • How to apply SAT-solving for the equivalence test of monotone normal forms
    Mundhenk, Zeranski. SAT, 2011.

  • The tractability of model-checking for LTL: the good, the bad, and the ugly fragments
    Bauland, Mundhenk, Schneider, H.Schnoor, I.Schnoor, Vollmer. ACM Transactions on Computational Logic (TOCL), 2011. [DOI] [ abstract ]

  • The model checking problem for propositional intuitionistic logic with one variable is AC1-complete
    Mundhenk, Weiß. STACS, 2011. [DOI]

  • The Complexity of Satisfiability for Fragments of Hybrid Logic - Part I
    Meier, Mundhenk, Schneider, Thomas, Weber, Weiß. MFCS 2009; Journal of Applied Logic, 2010. [DOI]

  • Complexity of hybrid logics over transitive frames
    Mundhenk, Schneider, Schwentick, Weber. Journal of Applied Logic, 2010. [DOI]

  • The complexity of model checking for intuitionistic logics and their modal companions
    Mundhenk, Weiß. Workshop on Reachability Problems, 2010.

  • Model checking CTL is almost always inherently sequential
    Beyersdorff, Meier, Thomas, Vollmer, Mundhenk, Schneider. 16th Symp. on Temporal Representation and Reasoning (TIME), 2009.

  • Experimental comparison of the two Fredman-Khachiyan-algorithms
    Hagen, Horatschek, Mundhenk. Workshop on Algorithm Engineering & Experiments (ALENEX), 2009. [ abstract ]

  • The complexity of satisfiability for fragments of CTL and CTL*
    Meier, Mundhenk, Thomas, Vollmer. 2nd Workshop on Reachability Problems (2008); Intl.J.of Foundations of Computer Science, 2009. [ abstract ]

  • Complexity of DNF minimization and isomorphism testing for monotone formulas
    Hagen, Mundhenk, Goldsmith. Information and Computation 206(6), pp.760-775, 2008. [ abstract ]

  • The tractability of model-checking for LTL: the good, the bad, and the ugly fragments
    Bauland, Mundhenk, Schneider, H.Schnoor, I.Schnoor, Vollmer. Methods for Modalities (2007), ENTCS 231, 2009. [ abstract ]

  • Competition adds complexity
    Goldsmith, Mundhenk. 21st Conf. on Neural Information Processing Systems, 2007. [ abstract ]

  • The complexity of hybrid logics over equivalence relations
    Mundhenk, Schneider. Workshop on Hybrid Logic (2007); Journal of Logic, Languange and Information 18:493-514, 2009. [ abstract ]

  • Complexity of hybrid logics over transitive frames
    Mundhenk, Schneider, Schwentick, Weber. Methods for Modalities, 2005. [ abstract ]

  • Undecidability of multi-modal hybrid logics
    Mundhenk, Schneider. Int. Workshop on Hybrid Logic, ENTCS 174(6), pp.29-43, 2006. [ abstract ]

  • Mathematische Grundlagen der Informatik - Mathematisches Denken und Beweisen
    Meinel, Mundhenk. Teubner Verlag, 4.Auflage, 2009.

  • A Distributed Meta Level Architecture for the Self-Organizing Grid of Services
    Beckstein, Dittrich, Erfurth, Fey, König-Ries, Mundhenk, Sack. Proc. Mobile Services and Ontologies Workshop (MoSO 2006), held as part of the 7th International Conference on Mobile Data Management (MDM'06), 2006.

  • Complexity of DNF and isomorphism of monotone formulas
    Goldsmith, Hagen, Mundhenk. MFCS, 2005. [ abstract ]

  • The complexity of planning with partially observable Markov decision processes
    Mundhenk. Habilitationsschrift, 2001. [ abstract ]

  • Creating a virtual library with HomePageSearch and Mops
    Hoff, Mundhenk. ACM SIGDOC, 2001. [ abstract ]

  • Nonapproximability results for partially observable Markov decision processes
    Lusena, Goldsmith, Mundhenk. Journal on Artificial Intelligence Research , Vol. 14, 2001. [ abstract ]

  • On hard instances
    Mundhenk. Theoretical Computer Science, 242(1-2), 2000. [ abstract ]

  • Complexity of finite-horizon Markov decision process problems
    Mundhenk, Goldsmith, Lusena, Allender. Journal of the ACM , 47(4), 2000. [ abstract ]

  • The complexity of optimal small policies
    Mundhenk. Mathematics of Operations Research, 25(1), 2000. [ abstract ]

  • Nondeterministic instance complexity and hard-to-prove tautologies
    Arvind, Köbler, Mundhenk, Torán. STACS, 2000. [ abstract ]

  • Complexity of propositional proof systems: tableaux, resolution, cutting-planes
    Mundhenk. Course notes for 11th European Summerschool on Logic, Language, and Information (ESSLLI) , 1999.

  • Hard instances of NP-hard sets
    Mundhenk. Journées de l'Informatique Messine, 1999. [ abstract ]

  • Complexity issues in Markov decision processes
    Goldsmith, Mundhenk. Proc. of 13th Conference on Computational Complexity, 1998.

  • Survey on Optimal non-approximability of Max-Clique
    Mundhenk, Slobodová. In: Mayr, Prömel, Steger (eds.): Lectures on proof verification and approximation algorithms , LNCS 1367, Springer Verlag, 1998.

  • The computational complexity of probabilistic planning
    Littman, Goldsmith, Mundhenk. Journal on Artificial Intelligence Research , Vol.9, 1998. [ abstract ]

  • The complexity of plan existence and evaluation in probabilistic domains
    Goldsmith, Littman, Mundhenk. Proc. of Uncertainty in AI, 1997.

  • The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes
    Mundhenk, Goldsmith, Allender. Proc. of MFCS, 1997. [ abstract ]

  • Monotonous and randomized reductions to sparse sets
    Arvind, Köbler, Mundhenk. RAIRO Theoretical Informatics and Applications 30, 1996. [ abstract ]

  • Survey on Limited nondeterminism
    Goldsmith, Levy, Mundhenk. SIGACT News, June 1996 .

  • Upper bounds for the complexity of sparse and tally descriptions
    Arvind, Köbler, Mundhenk. Mathematical Systems Theory 29, 1996. [ abstract ]

  • On reductions to sets that avoid EXPSPACE
    Arvind, Köbler, Mundhenk. Information Processing Letters 65, 1995. [ abstract ]

  • On monotonous oracle machines
    Mundhenk. LATIN , 1995. [ abstract ]

  • On self-reducible sets of low information content
    Mundhenk. CIAC, 1994. [ abstract ]

  • Hausdorff reductions to sparse sets and to sets of high information content
    Arvind, Köbler, Mundhenk. MFCS, 1993. [ abstract ]

  • Hausdorff Reduktionen zu Mengen mit geringem Informationsgehalt
    Mundhenk. PhD thesis, 1993. [ abstract ]

  • Bounded truth-table and conjunctive reductions to sparse and tally sets
    Arvind, Köbler, Mundhenk. FST-TCS, 1992. [ abstract ]

  • Lowness and the complexity of sparse and tally descriptions
    Arvind, Köbler, Mundhenk. ISAAC, 1992. [ abstract ]

  • Reductions to sets of low information content
    Arvind, Han, Hemachandra, Köbler, Lozano, Mundhenk, Ogiwara, Schöning, Silvestri, Thierauf. ICALP, 1992. [ abstract ]

  • Random languages for non-uniform complexity classes
    Mundhenk, Schuler. Structures'90; Journal of Complexity, 1992. [ abstract ]

    • LNCS series homepage,
    Back to my homepage, to the Universität Jena Math/CS department homepage, or to the Friedrich-Schiller-Universität Jena homepage