2 Search Results for "Wiener, Thomas"

Document
DOI: 10.4230/LIPIcs.ECOOP.2023.21
Automata Learning with an Incomplete Teacher

Authors: Mark Moeller, Thomas Wiener, Alaia Solko-Breslin, Caleb Koch, Nate Foster, and Alexandra Silva

Published in: LIPIcs, Volume 263, 37th European Conference on Object-Oriented Programming (ECOOP 2023)

Abstract
The preceding decade has seen significant interest in use of active learning to build models of programs and protocols. But existing algorithms assume the existence of an idealized oracle - a so-called Minimally Adequate Teacher (MAT) - that cannot be fully realized in practice and so is usually approximated with testing. This work proposes a new framework for active learning based on an incomplete teacher. This new formulation, called iMAT, neatly handles scenarios in which the teacher has access to only a finite number of tests or otherwise has gaps in its knowledge. We adapt Angluin’s L^⋆ algorithm for learning finite automata to incomplete teachers and we build a prototype implementation in OCaml that uses an SMT solver to help fill in information not supplied by the teacher. We demonstrate the behavior of our iMAT prototype on a variety of learning problems from a standard benchmark suite.
Cite as

Mark Moeller, Thomas Wiener, Alaia Solko-Breslin, Caleb Koch, Nate Foster, and Alexandra Silva. Automata Learning with an Incomplete Teacher. In 37th European Conference on Object-Oriented Programming (ECOOP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 263, pp. 21:1-21:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{moeller_et_al:LIPIcs.ECOOP.2023.21,
  author =	{Moeller, Mark and Wiener, Thomas and Solko-Breslin, Alaia and Koch, Caleb and Foster, Nate and Silva, Alexandra},
  title =	{{Automata Learning with an Incomplete Teacher}},
  booktitle =	{37th European Conference on Object-Oriented Programming (ECOOP 2023)},
  pages =	{21:1--21:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-281-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{263},
  editor =	{Ali, Karim and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2023.21},
  URN =		{urn:nbn:de:0030-drops-182145},
  doi =		{10.4230/LIPIcs.ECOOP.2023.21},
  annote =	{Keywords: Finite Automata, Active Learning, SMT Solvers}
}
Document
DOI: 10.4230/DagSemProc.04401.6
Lower Bounds and Non-Uniform Time Discretization for Approximation of Stochastic Heat Equations

Authors: Klaus Ritter and Thomas Müller-Gronbach

Published in: Dagstuhl Seminar Proceedings, Volume 4401, Algorithms and Complexity for Continuous Problems (2005)

Abstract
We study algorithms for approximation of the mild solution of stochastic heat equations on the spatial domain ]0,1[^d. The error of an algorithm is defined in L_2-sense. We derive lower bounds for the error of every algorithm that uses a total of N evaluations of one-dimensional components of the driving Wiener process W. For equations with additive noise we derive matching upper bounds and we construct asymptotically optimal algorithms. The error bounds depend on N and d, and on the decay of eigenvalues of the covariance of W in the case of nuclear noise. In the latter case the use of non-uniform time discretizations is crucial.
Cite as

Klaus Ritter and Thomas Müller-Gronbach. Lower Bounds and Non-Uniform Time Discretization for Approximation of Stochastic Heat Equations. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, pp. 1-37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{ritter_et_al:DagSemProc.04401.6,
  author =	{Ritter, Klaus and M\"{u}ller-Gronbach, Thomas},
  title =	{{Lower Bounds and Non-Uniform Time Discretization for Approximation of Stochastic Heat Equations}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--37},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.6},
  URN =		{urn:nbn:de:0030-drops-1518},
  doi =		{10.4230/DagSemProc.04401.6},
  annote =	{Keywords: Stochastic heat equation , Non-uniform time discretization , minimal errors , upper and lower bounds}
}
  • Refine by Author
  • 1 Foster, Nate
  • 1 Koch, Caleb
  • 1 Moeller, Mark
  • 1 Müller-Gronbach, Thomas
  • 1 Ritter, Klaus
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Active learning

  • Refine by Keyword
  • 1 Active Learning
  • 1 Finite Automata
  • 1 Non-uniform time discretization
  • 1 SMT Solvers
  • 1 Stochastic heat equation
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2005
  • 1 2023

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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact