5 Search Results for "Wiener, Thomas"


Document
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
Artifact
Automata Learning with an Incomplete Teacher (Artifact)

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

Published in: DARTS, Volume 9, Issue 2, Special Issue of the 37th European Conference on Object-Oriented Programming (ECOOP 2023)


Abstract
We provide an implementation of the automata learning software described in the associated ECOOP article. In particular, the artifact is a Docker image with the source code for nerode and nerode-learn, along with the scripts and benchmark inputs needed to reproduce the experiments described in the paper.

Cite as

Mark Moeller, Thomas Wiener, Alaia Solko-Breslin, Caleb Koch, Nate Foster, and Alexandra Silva. Automata Learning with an Incomplete Teacher (Artifact). In Special Issue of the 37th European Conference on Object-Oriented Programming (ECOOP 2023). Dagstuhl Artifacts Series (DARTS), Volume 9, Issue 2, pp. 21:1-21:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{moeller_et_al:DARTS.9.2.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 (Artifact)}},
  pages =	{21:1--21:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2023},
  volume =	{9},
  number =	{2},
  editor =	{Moeller, Mark and Wiener, Thomas and Solko-Breslin, Alaia and Koch, Caleb and Foster, Nate and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.9.2.21},
  URN =		{urn:nbn:de:0030-drops-182612},
  doi =		{10.4230/DARTS.9.2.21},
  annote =	{Keywords: Finite Automata, Active Learning, SMT Solvers}
}
Document
Schematic Maps and Indoor Wayfinding

Authors: Christina Bauer and Bernd Ludwig

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)


Abstract
Schematic maps are often discussed as an adequate alternative of displaying wayfinding information compared to detailed map designs. However, these depictions have not yet been compared and analyzed in-depth. In this paper, we present a user study that evaluates the wayfinding behaviour of participants either using a detailed floor plan or a schematic map that only shows the route to follow and landmarks. The study was conducted in an indoor real-world scenario. The depictions were presented with the help of a mobile navigation system. We analyzed the time it took to understand the wayfinding instruction and the workload of the users. Moreover, we examined how the depictions were visually perceived with a mobile eye tracker. Results show that wayfinders who use the detailed map spend more visual attention on the instructions. Nevertheless, the depiction does not help to solve the task: they also needed more time to orient themselves. Regarding the workload and the wayfinding errors no differences were found.

Cite as

Christina Bauer and Bernd Ludwig. Schematic Maps and Indoor Wayfinding. In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.COSIT.2019.23,
  author =	{Bauer, Christina and Ludwig, Bernd},
  title =	{{Schematic Maps and Indoor Wayfinding}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.23},
  URN =		{urn:nbn:de:0030-drops-111157},
  doi =		{10.4230/LIPIcs.COSIT.2019.23},
  annote =	{Keywords: Wayfinding, schematic maps, eye tracking, indoor environment}
}
Document
The Eureka Programming Model for Speculative Task Parallelism

Authors: Shams Imam and Vivek Sarkar

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


Abstract
In this paper, we describe the Eureka Programming Model (EuPM) that simplifies the expression of speculative parallel tasks, and is especially well suited for parallel search and optimization applications. The focus of this work is to provide a clean semantics for, and efficiently support, such "eureka-style" computations (EuSCs) in general structured task parallel programming models. In EuSCs, a eureka event is a point in a program that announces that a result has been found. A eureka triggered by a speculative task can cause a group of related speculative tasks to become redundant, and enable them to be terminated at well-defined program points. Our approach provides a bound on the additional work done in redundant speculative tasks after such a eureka event occurs. We identify various patterns that are supported by our eureka construct, which include search, optimization, convergence, and soft real-time deadlines. These different patterns of computations can also be safely combined or nested in the EuPM, along with regular task-parallel constructs, thereby enabling high degrees of composability and reusability. As demonstrated by our implementation, the EuPM can also be implemented efficiently. We use a cooperative runtime that uses delimited continuations to manage the termination of redundant tasks and their synchronization at join points. In contrast to current approaches, EuPM obviates the need for cumbersome manual refactoring by the programmer that may (for example) require the insertion of if checks and early return statements in every method in the call chain. Experimental results show that solutions using the EuPM simplify programmability, achieve performance comparable to hand-coded speculative task-based solutions and out-perform non-speculative task-based solutions.

Cite as

Shams Imam and Vivek Sarkar. The Eureka Programming Model for Speculative Task Parallelism. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 421-444, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{imam_et_al:LIPIcs.ECOOP.2015.421,
  author =	{Imam, Shams and Sarkar, Vivek},
  title =	{{The Eureka Programming Model for Speculative Task Parallelism}},
  booktitle =	{29th European Conference on Object-Oriented Programming (ECOOP 2015)},
  pages =	{421--444},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-86-6},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{37},
  editor =	{Boyland, John Tang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.421},
  URN =		{urn:nbn:de:0030-drops-52327},
  doi =		{10.4230/LIPIcs.ECOOP.2015.421},
  annote =	{Keywords: Async-Finish Model, Delimited Continuations, Eureka Model, Parallel Programming, Speculative Parallelism, Task Cancellation, Task Termination}
}
Document
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
  • 2 Foster, Nate
  • 2 Koch, Caleb
  • 2 Moeller, Mark
  • 2 Silva, Alexandra
  • 2 Solko-Breslin, Alaia
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Active learning
  • 1 Human-centered computing → Empirical studies in HCI
  • 1 Information systems → Location based services

  • Refine by Keyword
  • 2 Active Learning
  • 2 Finite Automata
  • 2 SMT Solvers
  • 1 Async-Finish Model
  • 1 Delimited Continuations
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2023
  • 1 2005
  • 1 2015
  • 1 2019

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