2 Search Results for "Dietrich, Heiko"


Document
The Isomorphism Problem for Plain Groups Is in Σ₃^{𝖯}

Authors: Heiko Dietrich, Murray Elder, Adam Piggott, Youming Qiao, and Armin Weiß

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. Sénizergues and the fifth author (ICALP2018) proved that the isomorphism problem for virtually free groups is decidable in PSPACE when the input is given in terms of so-called virtually free presentations. Here we consider the isomorphism problem for the class of plain groups, that is, groups that are isomorphic to a free product of finitely many finite groups and finitely many copies of the infinite cyclic group. Every plain group is naturally and efficiently presented via an inverse-closed finite convergent length-reducing rewriting system. We prove that the isomorphism problem for plain groups given in this form lies in the polynomial time hierarchy, more precisely, in Σ₃^𝖯. This result is achieved by combining new geometric and algebraic characterisations of groups presented by inverse-closed finite convergent length-reducing rewriting systems developed in recent work of the second and third authors (2021) with classical finite group isomorphism results of Babai and Szemerédi (1984).

Cite as

Heiko Dietrich, Murray Elder, Adam Piggott, Youming Qiao, and Armin Weiß. The Isomorphism Problem for Plain Groups Is in Σ₃^{𝖯}. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dietrich_et_al:LIPIcs.STACS.2022.26,
  author =	{Dietrich, Heiko and Elder, Murray and Piggott, Adam and Qiao, Youming and Wei{\ss}, Armin},
  title =	{{The Isomorphism Problem for Plain Groups Is in \Sigma₃^\{𝖯\}}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.26},
  URN =		{urn:nbn:de:0030-drops-158368},
  doi =		{10.4230/LIPIcs.STACS.2022.26},
  annote =	{Keywords: plain group, isomorphism problem, polynomial hierarchy, \Sigma₃^\{𝖯\} complexity class, inverse-closed finite convergent length-reducing rewriting system}
}
Document
GoPubMed: Exploring Pubmed with Ontological Background Knowledge

Authors: Heiko Dietze, Dimitra Alexopoulou, Michael R. Alvers, Bill Barrio-Alvers, Andreas Doms, Jörg Hakenberg, Jan Mönnich, Conrad Plake, Andreas Reischuck, Loic Royer, Thomas Wächter, Matthias Zschunke, and Michael Schroeder

Published in: Dagstuhl Seminar Proceedings, Volume 8131, Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives (2008)


Abstract
With the ever increasing size of scientific literature, finding relevant documents and answering questions has become even more of a challenge. Recently, ontologies - hierarchical, controlled vocabularies - have been introduced to annotate genomic data. They can also improve the question answering and the selection of relevant documents in the literature search. Search engines such as GoPubMed.org use ontological background knowledge to give an overview over large query results and to help answering questions. We review the problems and solutions underlying these next generation intelligent search engines and give examples of the power of this new search paradigm.

Cite as

Heiko Dietze, Dimitra Alexopoulou, Michael R. Alvers, Bill Barrio-Alvers, Andreas Doms, Jörg Hakenberg, Jan Mönnich, Conrad Plake, Andreas Reischuk, Loic Royer, Thomas Wächter, Matthias Zschunke, and Michael Schroeder. GoPubMed: Exploring Pubmed with Ontological Background Knowledge. In Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives. Dagstuhl Seminar Proceedings, Volume 8131, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{dietze_et_al:DagSemProc.08131.6,
  author =	{Dietze, Heiko and Alexopoulou, Dimitra and Alvers, Michael R. and Barrio-Alvers, Bill and Doms, Andreas and Hakenberg, J\"{o}rg and M\"{o}nnich, Jan and Plake, Conrad and Reischuck, Andreas and Royer, Loic and W\"{a}chter, Thomas and Zschunke, Matthias and Schroeder, Michael},
  title =	{{GoPubMed: Exploring Pubmed with Ontological Background Knowledge}},
  booktitle =	{Ontologies and Text Mining for Life Sciences : Current Status and Future Perspectives},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8131},
  editor =	{Michael Ashburner and Ulf Leser and Dietrich Rebholz-Schuhmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08131.6},
  URN =		{urn:nbn:de:0030-drops-15204},
  doi =		{10.4230/DagSemProc.08131.6},
  annote =	{Keywords: Text mining, literature search, Gene Ontology, NLP, ontology, thesaurus, PubMed}
}
  • Refine by Author
  • 1 Alexopoulou, Dimitra
  • 1 Alvers, Michael R.
  • 1 Barrio-Alvers, Bill
  • 1 Dietrich, Heiko
  • 1 Dietze, Heiko
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Computability
  • 1 Theory of computation → Rewrite systems

  • Refine by Keyword
  • 1 Gene Ontology
  • 1 NLP
  • 1 PubMed
  • 1 Text mining
  • 1 inverse-closed finite convergent length-reducing rewriting system
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail