×

zbMATH — the first resource for mathematics

Mundhenk, Martin

Compute Distance To:
Author ID: mundhenk.martin Recent zbMATH articles by "Mundhenk, Martin"
Published as: Mundhenk, M.; Mundhenk, Martin
External Links: MGP
Documents Indexed: 47 Publications since 1991, including 5 Books

Publications by Year

Citations contained in zbMATH

34 Publications have been cited 144 times in 99 Documents Cited by Year
The computational complexity of probabilistic planning. Zbl 0903.68100
Littman, M. L.; Goldsmith, J.; Mundhenk, M.
24
1998
Reductions to sets of low information content. Zbl 0794.68058
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.
17
1993
Complexity of finite-horizon Markov decision process problems. Zbl 1327.68136
Mundhenk, Martin; Goldsmith, Judy; Lusena, Christopher; Allender, Eric
10
2000
The complexity of satisfiability for fragments of hybrid logic. I. Zbl 1215.03034
Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Weber, Volker; Weiss, Felix
7
2010
On the complexity of bribery and manipulation in tournaments with uncertain information. Zbl 1422.91225
Mattei, Nicholas; Goldsmith, Judy; Klapper, Andrew; Mundhenk, Martin
6
2015
Complexity of hybrid logics over transitive frames. Zbl 1215.03035
Mundhenk, Martin; Schneider, Thomas; Schwentick, Thomas; Weber, Volker
6
2010
The tractability of model-checking for LTL: the good, the bad, and the ugly fragments. Zbl 1347.68217
Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert
6
2009
Upper bounds for the complexity of sparse and tally descriptions. Zbl 0840.68041
Arvind, V.; Köbler, J.; Mundhenk, M.
6
1996
Model checking CTL is almost always inherently sequential. Zbl 1220.68068
Beyersdorff, Olaf; Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Vollmer, Heribert
5
2011
The complexity of satisfiability for fragments of CTL and CTL\(^\bigstar \). Zbl 1186.68212
Meier, Arne; Thomas, Michael; Vollmer, Heribert; Mundhenk, Martin
5
2009
On bounded truth-table, conjunctive, and randomized reductions to sparse sets. Zbl 0919.03034
Arvind, V.; Köbler, J.; Mundhenk, M.
5
1992
The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\). Zbl 1337.68134
Meier, Arne; Mundhenk, Martin; Thomas, Michael; Vollmer, Heribert
4
2008
Undecidability of multi-modal hybrid logics. Zbl 1278.03047
Mundhenk, Martin; Schneider, Thomas
4
2007
The tractability of model checking for LTL: the good, the bad, and the ugly fragments. Zbl 1351.68151
Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert
3
2011
Nonapproximability results for partially observable Markov decision processes. Zbl 1042.90052
Lusena, C.; Goldsmith, J.; Mundhenk, M.
3
2001
Complexity issues in Markov decision processes. Zbl 0935.68045
Goldsmith, Judy; Mundhenk, Martin
3
1998
The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes. Zbl 0947.90599
Mundhenk, Martin; Goldsmith, Judy; Allender, Eric
3
1997
Erratum to: “The complexity of satisfiability for fragments of CTL and \(\mathrm{CTL}^\star\)”. Zbl 1405.68130
Meier, Arne; Thomas, Michael; Vollmer, Heribert; Mundhenk, Martin
2
2015
An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic. Zbl 06374277
Mundhenk, Martin; Wei, Felix
2
2014
Intuitionistic implication makes model checking hard. Zbl 1237.68125
Mundhenk, Martin; Weiss, Felix
2
2012
The complexity of model checking for intuitionistic logics and their modal companions. Zbl 1287.68110
Mundhenk, Martin; Weiß, Felix
2
2010
The complexity of satisfiability for fragments of hybrid logic. I. Zbl 1250.03036
Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Weber, Volker; Weiss, Felix
2
2009
Complexity of DNF minimization and isomorphism testing for monotone formulas. Zbl 1152.68021
Goldsmith, Judy; Hagen, Matthias; Mundhenk, Martin
2
2008
Complexity of DNF and isomorphism of monotone formulas. Zbl 1156.68401
Goldsmith, Judy; Hagen, Matthias; Mundhenk, Martin
2
2005
Nondeterministic instance complexity and hard-to-prove tautologies. Zbl 0962.68154
Arvind, Vikraman; Köbler, Johannes; Mundhenk, Martin; Torán, Jacobo
2
2000
Lowness and the complexity of sparse and tally descriptions. Zbl 0925.68214
Arvind, V.; Koebler, J.; Mundhenk, M.
2
1992
Random languages for nonuniform complexity classes. Zbl 0796.68097
Mundhenk, Martin; Schuler, Rainer
2
1991
The complexity of primal logic with disjunction. Zbl 1327.68120
Magirius, Marco; Mundhenk, Martin; Palenta, Raphaela
1
2015
Complexity of model checking for logics over Kripke models. Zbl 1394.68233
Meier, Arne; Müller, Julian-Steffen; Mundhenk, Martin; Vollmer, Heribert
1
2012
The model checking problem for propositional intuitionistic logic with one variable is \(\text{AC}^1\)-complete. Zbl 1230.68145
Mundhenk, Martin; Weiß, Felix
1
2011
The complexity of hybrid logics over equivalence relations. Zbl 1193.03054
Mundhenk, Martin; Schneider, Thomas
1
2009
NP-hard sets have many hard instances. Zbl 0938.03061
Mundhenk, Martin
1
1997
Hausdorff reductions to sparse sets and to sets of high information content. Zbl 0925.03184
Arvind, V.; Köbler, J.; Mundhenk, M.
1
1993
Reductions to sets of low information content (extended abstract). Zbl 1425.68125
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.
1
1992
On the complexity of bribery and manipulation in tournaments with uncertain information. Zbl 1422.91225
Mattei, Nicholas; Goldsmith, Judy; Klapper, Andrew; Mundhenk, Martin
6
2015
Erratum to: “The complexity of satisfiability for fragments of CTL and \(\mathrm{CTL}^\star\)”. Zbl 1405.68130
Meier, Arne; Thomas, Michael; Vollmer, Heribert; Mundhenk, Martin
2
2015
The complexity of primal logic with disjunction. Zbl 1327.68120
Magirius, Marco; Mundhenk, Martin; Palenta, Raphaela
1
2015
An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic. Zbl 06374277
Mundhenk, Martin; Wei, Felix
2
2014
Intuitionistic implication makes model checking hard. Zbl 1237.68125
Mundhenk, Martin; Weiss, Felix
2
2012
Complexity of model checking for logics over Kripke models. Zbl 1394.68233
Meier, Arne; Müller, Julian-Steffen; Mundhenk, Martin; Vollmer, Heribert
1
2012
Model checking CTL is almost always inherently sequential. Zbl 1220.68068
Beyersdorff, Olaf; Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Vollmer, Heribert
5
2011
The tractability of model checking for LTL: the good, the bad, and the ugly fragments. Zbl 1351.68151
Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert
3
2011
The model checking problem for propositional intuitionistic logic with one variable is \(\text{AC}^1\)-complete. Zbl 1230.68145
Mundhenk, Martin; Weiß, Felix
1
2011
The complexity of satisfiability for fragments of hybrid logic. I. Zbl 1215.03034
Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Weber, Volker; Weiss, Felix
7
2010
Complexity of hybrid logics over transitive frames. Zbl 1215.03035
Mundhenk, Martin; Schneider, Thomas; Schwentick, Thomas; Weber, Volker
6
2010
The complexity of model checking for intuitionistic logics and their modal companions. Zbl 1287.68110
Mundhenk, Martin; Weiß, Felix
2
2010
The tractability of model-checking for LTL: the good, the bad, and the ugly fragments. Zbl 1347.68217
Bauland, Michael; Mundhenk, Martin; Schneider, Thomas; Schnoor, Henning; Schnoor, Ilka; Vollmer, Heribert
6
2009
The complexity of satisfiability for fragments of CTL and CTL\(^\bigstar \). Zbl 1186.68212
Meier, Arne; Thomas, Michael; Vollmer, Heribert; Mundhenk, Martin
5
2009
The complexity of satisfiability for fragments of hybrid logic. I. Zbl 1250.03036
Meier, Arne; Mundhenk, Martin; Schneider, Thomas; Thomas, Michael; Weber, Volker; Weiss, Felix
2
2009
The complexity of hybrid logics over equivalence relations. Zbl 1193.03054
Mundhenk, Martin; Schneider, Thomas
1
2009
The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\). Zbl 1337.68134
Meier, Arne; Mundhenk, Martin; Thomas, Michael; Vollmer, Heribert
4
2008
Complexity of DNF minimization and isomorphism testing for monotone formulas. Zbl 1152.68021
Goldsmith, Judy; Hagen, Matthias; Mundhenk, Martin
2
2008
Undecidability of multi-modal hybrid logics. Zbl 1278.03047
Mundhenk, Martin; Schneider, Thomas
4
2007
Complexity of DNF and isomorphism of monotone formulas. Zbl 1156.68401
Goldsmith, Judy; Hagen, Matthias; Mundhenk, Martin
2
2005
Nonapproximability results for partially observable Markov decision processes. Zbl 1042.90052
Lusena, C.; Goldsmith, J.; Mundhenk, M.
3
2001
Complexity of finite-horizon Markov decision process problems. Zbl 1327.68136
Mundhenk, Martin; Goldsmith, Judy; Lusena, Christopher; Allender, Eric
10
2000
Nondeterministic instance complexity and hard-to-prove tautologies. Zbl 0962.68154
Arvind, Vikraman; Köbler, Johannes; Mundhenk, Martin; Torán, Jacobo
2
2000
The computational complexity of probabilistic planning. Zbl 0903.68100
Littman, M. L.; Goldsmith, J.; Mundhenk, M.
24
1998
Complexity issues in Markov decision processes. Zbl 0935.68045
Goldsmith, Judy; Mundhenk, Martin
3
1998
The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes. Zbl 0947.90599
Mundhenk, Martin; Goldsmith, Judy; Allender, Eric
3
1997
NP-hard sets have many hard instances. Zbl 0938.03061
Mundhenk, Martin
1
1997
Upper bounds for the complexity of sparse and tally descriptions. Zbl 0840.68041
Arvind, V.; Köbler, J.; Mundhenk, M.
6
1996
Reductions to sets of low information content. Zbl 0794.68058
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.
17
1993
Hausdorff reductions to sparse sets and to sets of high information content. Zbl 0925.03184
Arvind, V.; Köbler, J.; Mundhenk, M.
1
1993
On bounded truth-table, conjunctive, and randomized reductions to sparse sets. Zbl 0919.03034
Arvind, V.; Köbler, J.; Mundhenk, M.
5
1992
Lowness and the complexity of sparse and tally descriptions. Zbl 0925.68214
Arvind, V.; Koebler, J.; Mundhenk, M.
2
1992
Reductions to sets of low information content (extended abstract). Zbl 1425.68125
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T.
1
1992
Random languages for nonuniform complexity classes. Zbl 0796.68097
Mundhenk, Martin; Schuler, Rainer
2
1991
all top 5

Cited by 181 Authors

14 Mundhenk, Martin
8 Meier, Arne
7 Schneider, Thomas
5 Hemaspaandra, Lane A.
5 Köbler, Johannes
4 Arvind, Vikraman
4 Thomas, Michael D.
4 Vollmer, Heribert
4 Weber, Volker
3 Beyersdorff, Olaf
3 Goldsmith, Judy
3 Mattei, Nicholas
3 Maua, Denis Deratani
3 Ogihara, Mitsunori
2 Aronshtam, Lior
2 Chatterjee, Krishnendu
2 Chmelík, Martin
2 Cucker, Felipe
2 Gagliardi Cozman, Fabio
2 Littman, Michael L.
2 Lohmann, Peter
2 Lück, Martin
2 Müller, Sebastian
2 Saad, Emad W.
2 Schnoor, Henning
2 Schnoor, Ilka
2 Shrot, Tammar
2 Stewart, Iain A.
2 Thomas, Michael A.
2 Toda, Seinosuke
2 Walsh, Toby
2 Weiss, Felix
1 Abbad, Mohammed
1 Agrawal, Manindra
1 Allender, Eric W.
1 Angiulli, Fabrizio
1 Aziz, Haris
1 Bailey, Delbert D.
1 Balcázar, José Luis
1 Bastani, Farokh B.
1 Bauland, Michael
1 Bertoli, Piergiorgio
1 Bidoit, Nicole
1 Binkele-Raible, Daniel
1 Bisset, Keith R.
1 Blondel, Vincent D.
1 Bonet, Blai
1 Brik, Alex
1 Bryce, Daniel
1 Cai, Jin-Yi
1 Calderon Jaramillo, Andres
1 Cao, Yi
1 Chakaravarthy, Venkatesan T.
1 Chang, Hyeong Soo
1 Chen, Jiangzhuo
1 Choi, Arthur
1 Cialdea Mayer, Marta
1 Cimatti, Alessandro
1 Cohen, Havazelet
1 Colazzo, Dario
1 Condon, Anne E.
1 Cozman, Fabio G.
1 Culberson, Joseph C.
1 Dalmau, Víctor
1 Daoui, Cherki
1 Darwiche, Adnan
1 Dastani, Mehdi M.
1 de Campos, Cassio Polpo
1 Dean, Thomas L.
1 Deodhar, Suruchi
1 Doder, Dragan
1 Dunne, Paul E.
1 Ebbing, Johannes
1 Eidelstein, Eitan
1 Eidelstein, Noa
1 Eiter, Thomas
1 Eiter, Thomas Walter
1 Erdélyi, Gábor
1 Faliszewski, Piotr
1 Feng, Xizhou
1 Fernau, Henning
1 Finkbeiner, Bernd
1 Fournier, Hervé
1 Fu, Jicheng
1 Gaspers, Serge
1 Gate, James
1 Geffner, Hector
1 Greco, Gianluigi
1 Guo, Xianping
1 Gupta, Raghav
1 Hagen, Matthias
1 Hanks, Steve
1 Harkins, Ryan C.
1 Hauch, Sascha
1 Hemaspaandra, Edith
1 Hermo, Montserrat
1 Hitchcock, John M.
1 Homer, Steven
1 Hutter, Marcus
1 Icard, Thomas F. III
...and 81 more Authors

Citations by Year