PUBLICATIONS
- V. Chepoi,
N. Creignou, M. Hermann, and
G. Salzer
The Helly property and satisfiability of Boolean formulas
defined on set families
European Journal of Combinatorics,
31(2):502-516, 2010.
DOI:
10.1016/j.ejc.2009.03.022
- M. Hermann
and
R. Pichler
Complexity of counting the optimal solutions
Theoretical Computer Science,
410(38-40):3814-3825, 2009.
DOI:
10.1016/j.tcs.2009.05.025
- A. J. Gil,
M. Hermann,
G. Salzer,
and
B. Zanuttini
Efficient algorithms for description problems over finite totally ordered domains
SIAM Journal on Computing,
38(3):922-945, 2008.
DOI:
10.1137/050635900
- M. Hermann
On Boolean primitive positive clones
Discrete Mathematics,
308(15):3151-3162, 2008.
DOI:
10.1016/j.disc.2007.06.018
- A. Durand
and
M. Hermann
On the counting complexity of propositional circumscription
Information Processing Letters,
106(4):164-170, 2008.
DOI:
10.1016/j.ipl.2007.11.006
- N. Creignou, M. Hermann,
A. Krokhin,
and
G. Salzer
Complexity of clausal constraints over chains
Theory of Computing Systems,
42(2):239-255, 2008.
DOI:
10.1007/s00224-007-9003-z
- A. Durand,
M. Hermann,
and
P. G. Kolaitis
Subtractive reductions and complete problems for
counting complexity classes
Theoretical Computer Science,
340(3):496-513, 2005.
DOI:
10.1016/j.tsc.2005.03.012
- A. Durand,
M. Hermann, and L. Juban
On the complexity of recognizing the Hilbert basis of a linear
Diophantine system
Theoretical Computer Science,
270(1-2):625-642, 2002.
DOI:
10.1016/S0304-3975(01)00017-2
- M. Hermann
and
P.G. Kolaitis
Unification algorithms cannot be combined in polynomial
time
Information and Computation ,
162(1-2):24-42, 2000.
DOI:
10.1006/inco.1999.2855
- M. Hermann
and
P.G. Kolaitis
Computational complexity of simultaneous elementary
matching problems
Journal of Automated Reasoning,
23(2):107-136, 1999.
DOI:
10.1023/A:1006136609427
- M. Hermann
and
R. Galbavý
Unification of infinite sets of terms schematized by
primal grammars
Theoretical Computer Science,
176(1-2):111-158, 1997.
DOI:
10.1016/S0304-3975(96)00052-7
- N. Creignou
and
M. Hermann
Complexity of generalized satisfiability counting problems
Information and Computation,
125(1):1-12, 1996.
DOI:
10.1006/inco.1996.0016
- M. Hermann
and
P.G. Kolaitis
The complexity of counting problems in equational matching
Journal of Symbolic Computation,
20(3):343-362, 1995.
DOI:
10.1006/jsco.1995.1054
- M. Hermann,
C. Kirchner,
and
H. Kirchner
Implementations of term rewriting systems
Computer Journal,
34(1):20-34, February 1991.
DOI:
10.1093/comjnl/34.1.20
Reviewed in
Computing Reviews,
February 1992; under the number 9202-0102.
- M. Hermann
Chain properties of rule closures
Formal Aspects of Computing,
2(3):207-225, 1990.
DOI:
10.1007/BF01888225
- A. Durand,
M. Hermann,
and
G. Nordh
Trichotomy in the complexity of minimal inference
24th Annual IEEE Symposium on
Logic in Computer Science
(LICS 2009),
Los Angeles (California, USA),
pages 387-396, August 2009.
DOI:
10.1109/LICS.2009.14
- M. Bodirsky,
M. Hermann,
and
F. Richoux
Complexity of existential positive first-order logic
In K. Ambos-Spies, B. Löwe, and W. Merkle, editors,
5th International Conference on Computability in Europe
(CiE
2009), Heidelberg (Germany),
volume 5635 of Lecture Notes in Computer Science, pages 31-36,
Springer-Verlag, July 2009.
DOI:
10.1007/978-3-642-03073-4_4
- M. Hermann
and
F. Richoux
On the computational complexity of monotone constraint satisfaction problems
In S. Das and R. Uehara, editors,
3rd Annual Workshop on Algorithms and Computation (WALCOM
2009),
Kolkata (India),
volume 5431 of Lecture Notes in Computer Science, pages 286-297,
Springer-Verlag, February 2009.
DOI:
10.1007/978-3-642-00202-1_25
- M. Hermann
and
R. Pichler
Counting complexity of minimal cardinality and minimal weight abduction
In S. Hölldobler, C. Lutz, and H. Wansing, editors,
11th European
Conference on Logics in Artificial Intelligence
(JELIA 2008),
Dresden (Germany),
volume 5092 of Lecture Notes in Artificial Intelligence, pages
206-218,
Springer-Verlag,
2008.
DOI:
10.1007/978-3-540-87803-2_18
- M. Hermann
and
F. Richoux
Sur la complexité
algorithmique des problèmes de satisfaction de contraintes
disjonctifs
In 4e Journées Francophones de
Programmation par Contraintes (JFPC 2008),
Nantes (France),
pages 209-218, June 2008.
- M. Hermann
and
R. Pichler
Complexity of counting the optimal solutions
In X. Hu and J. Wang, editors,
14th International Conference on Computing and Combinatorics
(COCOON 2008),
Dalian (China),
volume 5092 of Lecture Notes in Computer Science, pages 149-159,
Springer-Verlag,
June 2008.
DOI:
10.1007/978-3-540-69733-6_16
- V. Chepoi,
N. Creignou, M. Hermann, and
G. Salzer
Deciding the
satisfiability of propositional formulas in
finitely-valued signed logics
In G. W. Dueck, editor,
38th International Symposium on Multiple Valued Logic
(ISMVL 2008),
Dallas (Texas, USA),
IEEE Computer Society,
May 2008.
DOI:
10.1109/ISMVL.2008.41
- M. Hermann and B. Sertkaya
On the complexity of
computing generators of closed sets
In R. Medina and S. Obiedkov, editors,
6th International Conference on Formal Concept Analysis
(ICFCA
2008),
Montreal (Canada),
volume 4933 of Lecture Notes in Computer Science,
pages 158-168,
Springer-Verlag
February 2008.
DOI: 10.1007/978-3-540-78137-0_12
- Ph. Chapdelaine, M. Hermann, and I. Schnoor
Complexity of default logic
on generalized conjunctive queries
In Ch. Baral, G. Brewka, and J. Schlipf, editors,
9th International Conference on Logic
Programming and Nonmonotonic Reasoning
(LPNMR
2007),
Tempe (Arizona, USA),
volume 4483 of Lecture Notes in Artificial Intelligence,
pages 58-70.
Springer-Verlag
May 2007.
DOI: 10.1007/978-3-540-72200-7_7
- M. Hermann and R. Pichler
Counting complexity of propositional abduction
In M. M. Veloso, editor,
20th International Joint Conference on
Artificial Intelligence (IJCAI 2007),
Hyderabad (India),
pages 417-422.
January 2007.
- A. J. Gil, M. Hermann,
G. Salzer,
and B. Zanuttini
Efficient algorithms for
constraint description problems over
finite totally ordered domains (extended abstract)
In D. Basin and M. Rusinowitch, editors,
2nd International
Joint Conference on Automated Reasoning (IJCAR'04), Cork
(Ireland),
volume 3097
of Lecture
Notes in Computer Science, pages 244-258. Springer-Verlag, July 2004.
DOI: 10.1007/b98691
-
M. Bauland,
P. Chapdelaine,
N. Creignou, M. Hermann, and H. Vollmer
An algebraic approach to
the complexity of generalized conjunctive queries
In H. H. Hoos and D. G. Mitchell, editors,
7th International
Conference on Theory and Applications of Satisfiability Testing, (SAT 2004), Vancouver
(British Columbia, Canada),
volume 3542
of Lecture Notes
in Computer Science, pages 30-45, Springer-Verlag, May 2004.
DOI: 10.1007/11527695_3
- A. Durand and
M. Hermann
The inference problem for propositional circumscription of
affine formulas is coNP-complete
In H. Alt and M. Habib, editors,
20th Symposium on Theoretical Aspects of Computer Science
(STACS 2003),
Berlin (Germany),
volume 2607 of Lecture
Notes in Computer Science,
pages 451-462.
Springer-Verlag,
February 2003.
DOI: 10.1007/3-540-36494-3_40
- A. Durand,
M. Hermann, and P.G. Kolaitis
Subtractive reductions and complete problems for counting
complexity classes
In M. Nielsen and B. Rovan, editors,
25th International Symposium on Mathematical Foundations
of Computer Science (MFCS
2000), Bratislava (Slovakia),
volume 1893 of Lecture
Notes in Computer Science, pages 323-332. Springer-Verlag, August
2000.
DOI: 10.1007/3-540-44612-5_28
- M. Hermann, L. Juban, and P.G. Kolaitis
On the complexity of counting the Hilbert basis of a linear Diophantine system
In H. Ganzinger, D. McAllester, and A. Voronkov, editors,
6th International Conference on Logic for Programming and Automated Reasoning (LPAR'99), Tbilisi (Georgia),
volume 1705 of Lecture Notes in Computer Science (in Artificial Intelligence), pages 13-32. Springer-Verlag, September 1999.
Abstract
DOI: 10.1007/3-540-48242-3_2
- A. Durand, M. Hermann, and L. Juban
On the complexity of recognizing the Hilbert basis of a linear Diophantine system
In M. Kutylowski, L. Pacholski, and T. Wierzbicki, editors,
24th International Symposium on Mathematical Foundations of Computer Science (MFCS'99), Szklarska Poreba (Poland),
volume 1672 of Lecture Notes in Computer Science, pages 92-102. Springer-Verlag, September 1999.
Proofs in appendix
DOI: 10.1007/3-540-48340-3_9
- M. Hermann and G. Salzer
On the word, subsumption, and complement problem for recurrent term schematizations
In L. Brim, J. Gruska, and J. Zlatuska, editors,
23rd International Symposium on Mathematical Foundations of Computer Science (MFCS'98), Brno (Czech Republic),
volume 1450 of Lecture
Notes in Computer Science, pages 257-266. Springer-Verlag, August
1998.
DOI: 10.1007/BFb0055775
- M. Hermann and P.G. Kolaitis
On the complexity of unification and disunification in commutative idempotent semigroups
In G. Smolka, editor,
3rd International Conference on Principles and Practice of Constraint Programming (CP'97), Linz (Austria),
volume 1330 of Lecture
Notes in Computer Science, pages 283-297. Springer-Verlag, October
1997.
DOI: 10.1007/BFb0017446
- A. Amaniss, M. Hermann, and D. Lugiez
Set operations for recurrent term schematizations
In M. Bidoit and M. Dauchet, editors,
7th International Joint Conference on Theory and Practice of Software Development (TAPSOFT'97), Lille (France),
volume 1214 of Lecture
Notes in Computer Science, pages 333-344. Springer-Verlag, April
1997.
DOI: 10.1007/BFb0030608
- M. Hermann and P.G. Kolaitis
Unification algorithms cannot be combined in polynomial time
In M.A. McRobbie and J.K. Slaney, editors,
13th International Conference on
Automated Deduction (CADE'96), New Brunswick, NJ (USA),
volume 1104 of Lecture Notes in Computer Science (in Artificial Intelligence), pages 246-260. Springer-Verlag, July/August
1996.
DOI: 10.1007/3-540-61511-3_89
- M. Hermann and P.G. Kolaitis
Computational complexity of simultaneous elementary matching problems
In J. Wiedermann and P. Hájek, editors,
20th International Symposium on Mathematical Foundations of
Computer Science (MFCS'95), Prague (Czech Republic),
volume 969 of Lecture Notes in Computer Science, pages
359-370. Springer-Verlag,
August/September 1995.
DOI: 10.1007/3-540-60246-1_142
- M. Hermann and P.G. Kolaitis
The complexity of counting problems in equational matching
In A. Bundy, editor,
12th International Conference on Automated
Deduction (CADE'94), Nancy, (France),
volume 814 of Lecture
Notes in Computer Science (in Artificial Inteligence),
pages 560-574. Springer-Verlag, June
1994.
DOI: 10.1007/3-540-58156-1_41
- M. Hermann
On the relation between primitive recursion, schematization, and divergence
In H. Kirchner and G. Levi, editors,
3rd Conference on Algebraic and Logic
Programming (ALP'92), Volterra (Italy),
volume 632 of Lecture Notes in Computer Science, pages
115-127. Springer-Verlag,
September 1992.
DOI: 10.1007/BFb0013823
- M. Hermann
On proving properties of completion strategies
In R.V. Book, editor,
4th Conference on
Rewriting Techniques and Applications (RTA'91), Como (Italy),
volume 488 of Lecture Notes in Computer Science, pages
398-410. Springer-Verlag,
April 1991.
DOI: 10.1007/3-540-53904-2_113
- H. Kirchner and M. Hermann
Meta-rule synthesis from crossed rewrite systems
In S. Kaplan and M. Okada, editors,
2nd International Workshop on Conditional
and Typed Rewriting Systems (CTRS'90), Montreal (Canada),
volume 516 of Lecture Notes in Computer Science, pages
143-154. Springer-Verlag,
June 1990.
DOI: 10.1007/3-540-54317-1_87
- M. Hermann
Vademecum of divergent term rewriting systems
In Avancées en Programation
Journées AFCET-GROPLAN, Nice (France),
volume 70, pages 148-164. BIGRE, January 1990.
- M. Hermann
Chain properties of rule closures
In B. Monien and R. Cori, editors,
6th Annual
Symposium on Theoretical Aspects of Comupter Science (STACS'89),
Paderborn (Germany),
volume 349 of Lecture Notes in
Computer Science, pages 339-347. Springer-Verlag, February
1989.
DOI: 10.1007/BFb0028997
- M. Hermann and I. Prívara
On nontermination of Knuth-Bendix algorithm
In L. Kott, editor,
13th International Conference on Automata
Languages and Programming (ICALP'86), Rennes (France),
volume 226 of Lecture Notes in Computer Science, pages
146-156. Springer-Verlag,
July 1986.
DOI: 10.1007/3-540-16761-7_64
- F. Baader,
S. Ghilardi,
M. Hermann,
U. Sattler, and
V. Sofronie-Stokkermans (editors)
Complexity, Expressibility, and
Decidability in Automated Reasoning (CEDAR'08)
Workshop associated with
4th International Joint Conference on
Automated Reasoning (IJCAR
2008), Sydney (Australia),
August 2008.
- M. Hermann and G. Salzer (editors)
Term Schematizations and Their Applications
Workshop associated with
13th International Conference on Automated Deduction (CADE'96),
New Brunswick (New Jersey, USA),
July 1996.
Last modified: Sat Dec 5 11:14:08 CET 2009