3 Search Results for "Young, Michal"


Document
Unambiguous Catalytic Computation

Authors: Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)


Abstract
The catalytic Turing machine is a model of computation defined by Buhrman, Cleve, Koucký, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing machine, this model has an extra space which is filled with arbitrary content in addition to the clean space. In such a model we study if this additional filled space can be used to increase the power of computation or not, with the condition that the initial content of this extra filled space must be restored at the end of the computation. In this paper, we define the notion of unambiguous catalytic Turing machine and prove that under a standard derandomization assumption, the class of problems solved by an unambiguous catalytic Turing machine is same as the class of problems solved by a general nondeterministic catalytic Turing machine in the logspace setting.

Cite as

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Unambiguous Catalytic Computation. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2019.16,
  author =	{Gupta, Chetan and Jain, Rahul and Sharma, Vimal Raj and Tewari, Raghunath},
  title =	{{Unambiguous Catalytic Computation}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.16},
  URN =		{urn:nbn:de:0030-drops-115782},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.16},
  annote =	{Keywords: Catalytic computation, Logspace, Reinhardt-Allender}
}
Document
CUDA Accelerated LTL Model Checking -­ Revisited

Authors: Petr Bauch and Milan Ceska

Published in: OASIcs, Volume 16, Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers (2011)


Abstract
Recently, the massively parallel architecture has been used to significantly accelerate many computation demanding tasks. For example, in [Baier, Kateon, The MIT Press, 2009; Barnat, Brim, Ceska, ICPADS 2009] we have shown how CUDA technology can be employed to accelerate the process of Linear Temporal Logic (LTL) Model Checking. In this paper we redesign the One-Way-Catch-Them-Young (OWCTY) algorithm [Cerna, Pelanek, SPIN'03] in order to devise a new CUDA accelerated OWCTY algorithm that will significantly outperform the original CUDA accelerated algorithm and will be resistant to slowdown caused by improper ordering of the input data representation.

Cite as

Petr Bauch and Milan Ceska. CUDA Accelerated LTL Model Checking -­ Revisited. In Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers. Open Access Series in Informatics (OASIcs), Volume 16, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{bauch_et_al:OASIcs.MEMICS.2010.1,
  author =	{Bauch, Petr and Ceska, Milan},
  title =	{{CUDA Accelerated LTL Model Checking -­ Revisited}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{1--8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-22-4},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{16},
  editor =	{Matyska, Ludek and Kozubek, Michal and Vojnar, Tomas and Zemcik, Pavel and Antos, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.1},
  URN =		{urn:nbn:de:0030-drops-30729},
  doi =		{10.4230/OASIcs.MEMICS.2010.1},
  annote =	{Keywords: LTL Model Checking, CUDA, OWCTY}
}
Document
Computing and Diagnosing Changes in Unit Test Energy Consumption

Authors: Andrew J. Ko, Michal Young, Jamie Andrews, Brian P. Robinson, and Mark Grechanik

Published in: Dagstuhl Seminar Proceedings, Volume 10111, Practical Software Testing : Tool Automation and Human Factors (2010)


Abstract
Many developers have reason to be concerned with with power consumption. For example, mobile app developers want to minimize how much power their applications draw, while still providing useful functionality. However, developers have few tools to get feedback about changes to their application's power consumption behavior as they implement an application and make changes to it over time. We present a tool that, using a team's existing test cases, performs repeated measurements of energy consumption based on instructions executed, objects generated, and blocking latency, generating a distribution of energy use estimates for each test run, recording these distributions in a time series of distributions over time. Then, when these distributions change substantially, we inform the developer of this change, and offer them diagnostic information about the elements of their code potentially responsible for the change and the inputs responsible. Through this information, we believe that developers will be better enabled to relate recent changes in their code to changes in energy consumption, enabling them to better incorporate changes in software energy consumption into their software evolution decisions.

Cite as

Andrew J. Ko, Michal Young, Jamie Andrews, Brian P. Robinson, and Mark Grechanik. Computing and Diagnosing Changes in Unit Test Energy Consumption. In Practical Software Testing : Tool Automation and Human Factors. Dagstuhl Seminar Proceedings, Volume 10111, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{ko_et_al:DagSemProc.10111.4,
  author =	{Ko, Andrew J. and Young, Michal and Andrews, Jamie and Robinson, Brian P. and Grechanik, Mark},
  title =	{{Computing and Diagnosing Changes in Unit Test Energy Consumption}},
  booktitle =	{Practical Software Testing : Tool Automation and Human Factors},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10111},
  editor =	{Mark Harman and Henry Muccini and Wolfram Schulte and Tao Xie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10111.4},
  URN =		{urn:nbn:de:0030-drops-26248},
  doi =		{10.4230/DagSemProc.10111.4},
  annote =	{Keywords: Energy, oracles}
}
  • Refine by Author
  • 1 Andrews, Jamie
  • 1 Bauch, Petr
  • 1 Ceska, Milan
  • 1 Grechanik, Mark
  • 1 Gupta, Chetan
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing

  • Refine by Keyword
  • 1 CUDA
  • 1 Catalytic computation
  • 1 Energy
  • 1 LTL Model Checking
  • 1 Logspace
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2010
  • 1 2011
  • 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