3 Search Results for "Tollk�tter, Andreas"


Document
State Space Reduction For Parity Automata

Authors: Christof Löding and Andreas Tollkötter

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)


Abstract
Exact minimization of ω-automata is a difficult problem and heuristic algorithms are a subject of current research. We propose several new approaches to reduce the state space of deterministic parity automata. These are based on extracting information from structures within the automaton, such as strongly connected components, coloring of the states, and equivalence classes of given relations, to determine states that can safely be merged. We also establish a framework to generalize the notion of quotient automata and uniformly describe such algorithms. The description of these procedures consists of a theoretical analysis as well as data collected from experiments.

Cite as

Christof Löding and Andreas Tollkötter. State Space Reduction For Parity Automata. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{loding_et_al:LIPIcs.CSL.2020.27,
  author =	{L\"{o}ding, Christof and Tollk\"{o}tter, Andreas},
  title =	{{State Space Reduction For Parity Automata}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.27},
  URN =		{urn:nbn:de:0030-drops-116701},
  doi =		{10.4230/LIPIcs.CSL.2020.27},
  annote =	{Keywords: automata, \omega-automata, parity, minimization, state space reduction, deterministic, simulation relations}
}
Document
Transformation Between Regular Expressions and omega-Automata

Authors: Christof Löding and Andreas Tollkötter

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
We propose a new definition of regular expressions for describing languages of omega-words, called infinity-regular expressions. These expressions are obtained by adding to the standard regular expression on finite words an operator infinity that acts similar to the Kleene-star but can be iterated finitely or infinitely often (as opposed to the omega-operator from standard omega-regular expressions, which has to be iterated infinitely often). We show that standard constructions between automata and regular expressions for finite words can smoothly be adapted to infinite words in this setting: We extend the Glushkov construction yielding a simple translation of infinity-regular expressions into parity automata, and we show how to translate parity automata into infinity-regular expressions by the classical state elimination technique, where in both cases the nesting of the * and the infinity operators corresponds to the priority range used in the parity automaton. We also briefly discuss the concept of deterministic expressions that directly transfers from standard regular expressions to infinity-regular expressions.

Cite as

Christof Löding and Andreas Tollkötter. Transformation Between Regular Expressions and omega-Automata. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 88:1-88:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{loding_et_al:LIPIcs.MFCS.2016.88,
  author =	{L\"{o}ding, Christof and Tollk\"{o}tter, Andreas},
  title =	{{Transformation Between Regular Expressions and omega-Automata}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{88:1--88:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.88},
  URN =		{urn:nbn:de:0030-drops-64962},
  doi =		{10.4230/LIPIcs.MFCS.2016.88},
  annote =	{Keywords: infinity regular expressions, parity automata}
}
Document
ModeScore: A Method to Infer Changed Activity of Metabolic Function from Transcript Profiles

Authors: Andreas Hoppe and Hermann-Georg Holzhütter

Published in: OASIcs, Volume 26, German Conference on Bioinformatics 2012


Abstract
Genome-wide transcript profiles are often the only available quantitative data for a particular perturbation of a cellular system and their interpretation with respect to the metabolism is a major challenge in systems biology, especially beyond on/off distinction of genes. We present a method that predicts activity changes of metabolic functions by scoring reference flux distributions based on relative transcript profiles, providing a ranked list of most regulated functions. Then, for each metabolic function, the involved genes are ranked upon how much they represent a specific regulation pattern. Compared with the naïve pathway-based approach, the reference modes can be chosen freely, and they represent full metabolic functions, thus, directly provide testable hypotheses for the metabolic study. In conclusion, the novel method provides promising functions for subsequent experimental elucidation together with outstanding associated genes, solely based on transcript profiles.

Cite as

Andreas Hoppe and Hermann-Georg Holzhütter. ModeScore: A Method to Infer Changed Activity of Metabolic Function from Transcript Profiles. In German Conference on Bioinformatics 2012. Open Access Series in Informatics (OASIcs), Volume 26, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{hoppe_et_al:OASIcs.GCB.2012.1,
  author =	{Hoppe, Andreas and Holzh\"{u}tter, Hermann-Georg},
  title =	{{ModeScore: A Method to Infer Changed Activity of Metabolic Function from Transcript Profiles}},
  booktitle =	{German Conference on Bioinformatics 2012},
  pages =	{1--11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-44-6},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{26},
  editor =	{B\"{o}cker, Sebastian and Hufsky, Franziska and Scheubert, Kerstin and Schleicher, Jana and Schuster, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2012.1},
  URN =		{urn:nbn:de:0030-drops-37134},
  doi =		{10.4230/OASIcs.GCB.2012.1},
  annote =	{Keywords: Metabolic network, expression profile, metabolic function}
}
  • Refine by Author
  • 2 Löding, Christof
  • 2 Tollkötter, Andreas
  • 1 Holzhütter, Hermann-Georg
  • 1 Hoppe, Andreas

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Formal languages and automata theory
  • 1 Theory of computation → Regular languages

  • Refine by Keyword
  • 1 Metabolic network
  • 1 automata
  • 1 deterministic
  • 1 expression profile
  • 1 infinity regular expressions
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2012
  • 1 2016
  • 1 2020

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