OASIcs, Volume 16

Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers



Thumbnail PDF

Event

MEMICS 2010, October 22-24, 2010, Mikulov, Czech Republic

Editors

Ludek Matyska
Michal Kozubek
Tomas Vojnar
Pavel Zemcik
David Antos

Publication Details

  • published at: 2011-03-11
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
  • ISBN: 978-3-939897-22-4
  • DBLP: db/conf/memics/memics2010

Access Numbers

Documents

No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 16, MEMICS'10, Complete Volume

Authors: Ludek Matyska, Michal Kozubek, Tomáš Vojnar, Pavel Zemcík, and David Antos


Abstract
OASIcs, Volume 16, MEMICS'10, Complete Volume

Cite as

Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers. Open Access Series in Informatics (OASIcs), Volume 16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@Proceedings{matyska_et_al:OASIcs.MEMICS.2010,
  title =	{{OASIcs, Volume 16, MEMICS'10, Complete Volume}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-22-4},
  ISSN =	{2190-6807},
  year =	{2012},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010},
  URN =		{urn:nbn:de:0030-drops-35789},
  doi =		{10.4230/OASIcs.MEMICS.2010},
  annote =	{Keywords: Control structures and microprogramming, Input/output and data communications, Integrated circuits, Performance and reliability}
}
Document
Front Matter
Frontmatter, Preface, Table of Contents, Workshop Organization

Authors: Ludek Matyska, Michal Kozubek, Tomas Vojnar, Pavel Zemcik, and David Antos


Abstract
Frontmatter, Preface, Table of Contents, Workshop Organization

Cite as

Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers. Open Access Series in Informatics (OASIcs), Volume 16, pp. i-viii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{matyska_et_al:OASIcs.MEMICS.2010.i,
  author =	{Matyska, Ludek and Kozubek, Michal and Vojnar, Tomas and Zemcik, Pavel and Antos, David},
  title =	{{Frontmatter, Preface, Table of Contents, Workshop Organization}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{i--viii},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.i},
  URN =		{urn:nbn:de:0030-drops-30574},
  doi =		{10.4230/OASIcs.MEMICS.2010.i},
  annote =	{Keywords: Frontmatter, Preface, Table of Contents, Workshop Organization}
}
Document
CUDA Accelerated LTL Model Checking -­ Revisited

Authors: Petr Bauch and Milan Ceska


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.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
Process Algebra for Modal Transition Systemses

Authors: Nikola Benes and Jan Kretinsky


Abstract
The formalism of modal transition systems (MTS) is a well established framework for systems specification as well as abstract interpretation. Nevertheless, due to incapability to capture some useful features, various extensions have been studied, such as e.g. mixed transition systems or disjunctive MTS. Thus a need to compare them has emerged. Therefore, we introduce transition system with obligations as a general model encompassing all the aforementioned models, and equip it with a process algebra description. Using these instruments, we then compare the previously studied subclasses and characterize their relationships.

Cite as

Nikola Benes and Jan Kretinsky. Process Algebra for Modal Transition Systemses. 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. 9-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{benes_et_al:OASIcs.MEMICS.2010.9,
  author =	{Benes, Nikola and Kretinsky, Jan},
  title =	{{Process Algebra for Modal Transition Systemses}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{9--18},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.9},
  URN =		{urn:nbn:de:0030-drops-30701},
  doi =		{10.4230/OASIcs.MEMICS.2010.9},
  annote =	{Keywords: modal transition systems, process algebra, specification}
}
Document
A Simple Topology Preserving Max-Flow Algorithm for Graph Cut Based Image Segmentation

Authors: Ondrej Danek and Martin Maska


Abstract
In this paper, we propose a modification to the Boykov-Kolmogorov maximum flow algorithm [Boykov, Kolmogorv, IEEE 2004] in order to make the algorithm preserve the topology of an initial interface. This algorithm is being widely used in computer vision and image processing fields for its efficiency and speed when dealing with problems such as graph cut based image segmentation. Using our modification we are able to incorporate a topology prior into the algorithm allowing us to apply it in situations in which the inherent topological flexibility of graph cuts is inconvenient (e.g., biomedical image segmentation). Our approach exploits the simple point concept from digital geometry and is simpler and more straightforward to implement than previously introduced methods [Zeng, Samaras, Chen, Peng, Computer Vision and Image Understanding, 2008]. Due to the NP-completeness of the topology preserving problem our algorithm is only an approximation and is initialization dependent. However, promising results are demonstrated on graph cut based segmentation of both synthetic and real image data.

Cite as

Ondrej Danek and Martin Maska. A Simple Topology Preserving Max-Flow Algorithm for Graph Cut Based Image Segmentation. 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. 19-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{danek_et_al:OASIcs.MEMICS.2010.19,
  author =	{Danek, Ondrej and Maska, Martin},
  title =	{{A Simple Topology Preserving Max-Flow Algorithm for Graph Cut Based Image Segmentation}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{19--25},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.19},
  URN =		{urn:nbn:de:0030-drops-30695},
  doi =		{10.4230/OASIcs.MEMICS.2010.19},
  annote =	{Keywords: maximum flow, topology preserving, image segmentation, graph cuts}
}
Document
Haptic Rendering Based on RBF Approximation from Dynamically Updated Data

Authors: Jan Fousek, Tomas Golembiovsky, Jiri Filipovic, and Igor Peterlik


Abstract
In this paper, an extension of our previous research focused on haptic rendering based on interpolation from precomputed data is presented. The technique employs the radial-basis function (RBF) interpolation to achieve the accuracy of the force response approximation, however, it assumes that the data used by the interpolation method are generated on-the-fly during the haptic interaction. The issue caused by updating the RBF coefficients during the interaction is analyzed and a force-response smoothing strategy is proposed.

Cite as

Jan Fousek, Tomas Golembiovsky, Jiri Filipovic, and Igor Peterlik. Haptic Rendering Based on RBF Approximation from Dynamically Updated Data. 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. 26-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{fousek_et_al:OASIcs.MEMICS.2010.26,
  author =	{Fousek, Jan and Golembiovsky, Tomas and Filipovic, Jiri and Peterlik, Igor},
  title =	{{Haptic Rendering Based on RBF Approximation from Dynamically Updated Data}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{26--31},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.26},
  URN =		{urn:nbn:de:0030-drops-30592},
  doi =		{10.4230/OASIcs.MEMICS.2010.26},
  annote =	{Keywords: haptic rendering, radial-basis function approximation, precomputation, deformation modeling}
}
Document
Modeling Gene Networks using Fuzzy Logic

Authors: Artur Gintrowski


Abstract
Recently, almost uncontrolled technological progress allows so called high-throughput data collection for sophisticated and complex experimental biological systems analysis. Especially, it concerns the whole cellular genome. Therefore it becomes more and more vital to suggest and elaborate gene network models, which can be used for more complete interpretation of large and complex data sets. The presented paper concerns modeling of interactions in yeast genome. With the reference to previously published papers concerning the same subject, our paper presents a significant improvement in calculation procedure leading to very effective reduction of time of calculation.

Cite as

Artur Gintrowski. Modeling Gene Networks using Fuzzy Logic. 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. 32-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{gintrowski:OASIcs.MEMICS.2010.32,
  author =	{Gintrowski, Artur},
  title =	{{Modeling Gene Networks using Fuzzy Logic}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{32--39},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.32},
  URN =		{urn:nbn:de:0030-drops-30749},
  doi =		{10.4230/OASIcs.MEMICS.2010.32},
  annote =	{Keywords: Fuzzy network, gene expression, time optimization}
}
Document
Compression of Vector Field Changing in Time

Authors: Tomas Golembiovsky and Ales Krenek


Abstract
One of the problems connected with a real-time protein-ligand docking simulation is the need to store series of precomputed electrostatic force fields of a molecule changing in time. A single frame of the force field is a 3D array of floating point vectors and it constitutes approximately 180 MB of data. Therefore requirements on storage grow rapidly if several hundreds of such frames need to be stored. We propose a lossy compression method of such force field, based on audio and video coding, and we evaluate its properties and performance.

Cite as

Tomas Golembiovsky and Ales Krenek. Compression of Vector Field Changing in Time. 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. 40-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{golembiovsky_et_al:OASIcs.MEMICS.2010.40,
  author =	{Golembiovsky, Tomas and Krenek, Ales},
  title =	{{Compression of Vector Field Changing in Time}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{40--46},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.40},
  URN =		{urn:nbn:de:0030-drops-30640},
  doi =		{10.4230/OASIcs.MEMICS.2010.40},
  annote =	{Keywords: Protein-ligand docking, vector compression}
}
Document
Automatic C Compiler Generation from Architecture Description Language ISAC

Authors: Adam Husar, Miloslav Trmac, Jan Hranac, Tomas Hruska, and Karel Masarik


Abstract
This paper deals with retargetable compiler generation. After an introduction to application-specific instruction set processor design and a review of code generation in compiler backends, ISAC architecture description language is introduced. Automatic approach to instruction semantics extraction from ISAC models which result is usable for backend generation is presented. This approach was successfully tested on three models of MIPS, ARM and TI MSP430 architectures. Further backend generation process that uses extracted instruction is semantics presented. This process was currently tested on the MIPS architecture and some preliminary results are shown.

Cite as

Adam Husar, Miloslav Trmac, Jan Hranac, Tomas Hruska, and Karel Masarik. Automatic C Compiler Generation from Architecture Description Language ISAC. 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. 47-53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{husar_et_al:OASIcs.MEMICS.2010.47,
  author =	{Husar, Adam and Trmac, Miloslav and Hranac, Jan and Hruska, Tomas and Masarik, Karel},
  title =	{{Automatic C Compiler Generation from Architecture Description Language ISAC}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{47--53},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.47},
  URN =		{urn:nbn:de:0030-drops-30654},
  doi =		{10.4230/OASIcs.MEMICS.2010.47},
  annote =	{Keywords: ISAC architecture, compiler generation}
}
Document
Efficient Computation of Morphological Greyscale Reconstruction

Authors: Pavel Karas


Abstract
Morphological reconstruction is an important image operator from mathematical morphology. It is very often used for filtering, segmentation, and feature extraction. However, its computation can be very time-consuming for some input data. In this paper we review several efficient algorithms to compute the reconstruction, and compare their performance on real 3D images of large sizes. Furthermore, we propose a GPU implementation which performs up to 15x faster than the CPU methods. To our best knowledge, this is the first GPU implementation of the morphological reconstruction, described in literature.

Cite as

Pavel Karas. Efficient Computation of Morphological Greyscale Reconstruction. 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. 54-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{karas:OASIcs.MEMICS.2010.54,
  author =	{Karas, Pavel},
  title =	{{Efficient Computation of Morphological Greyscale Reconstruction}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{54--61},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.54},
  URN =		{urn:nbn:de:0030-drops-30679},
  doi =		{10.4230/OASIcs.MEMICS.2010.54},
  annote =	{Keywords: GPU, morphological reconstruction}
}
Document
On Reliability and Refutability in Nonconstructive Identification

Authors: Ilja Kucevalovs


Abstract
Identification in the limit, originally due to Gold [Gold, Information and Control, 1967], is a widely used computation model for inductive inference and human language acquisition. We consider a nonconstructive extension to Gold's model. Our current topic is the problem of applying the notions of reliability and refutability to nonconstructive identification. Four general identification situations are defined and two of them are studied. Thus some questions left open in [Kucevalovs, 2010] are now closed.

Cite as

Ilja Kucevalovs. On Reliability and Refutability in Nonconstructive Identification. 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. 62-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{kucevalovs:OASIcs.MEMICS.2010.62,
  author =	{Kucevalovs, Ilja},
  title =	{{On Reliability and Refutability in Nonconstructive Identification}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{62--68},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.62},
  URN =		{urn:nbn:de:0030-drops-30717},
  doi =		{10.4230/OASIcs.MEMICS.2010.62},
  annote =	{Keywords: inductive inference, identification, reliability, refutability, nonconstructive computation}
}
Document
Simultaneous Tracking of Multiple Objects Using Fast Level Set-Like Algorithm

Authors: Martin Maska, Pavel Matula, and Michal Kozubek


Abstract
A topological flexibility of implicit active contours is of great benefit, since it allows simultaneous detection of several objects without any a priori knowledge about their number and shapes. However, in tracking applications it is often required to keep desired objects mutually separated as well as allow each object to evolve itself, i.e., different objects cannot be merged together, but each object can split into several regions that can be merged again later in time. The former can be achieved by applying topology-preserving constraints exploiting either various repelling forces or the simple point concept from digital geometry, which brings, however, an indispensable increase in the execution time and also prevent the latter. In this paper, we propose more efficient and more flexible topology-preserving constraint based on a region indication function, that can be easily integrated into a fast level set-like algorithm [Maska, Matula, Danek, Kozubek, LNCS 6455, 2010] in order to obtain a fast and robust algorithm for simultaneous tracking of multiple objects. The potential of the modified algorithm is demonstrated on both synthetic and real image data.

Cite as

Martin Maska, Pavel Matula, and Michal Kozubek. Simultaneous Tracking of Multiple Objects Using Fast Level Set-Like Algorithm. 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. 69-76, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{maska_et_al:OASIcs.MEMICS.2010.69,
  author =	{Maska, Martin and Matula, Pavel and Kozubek, Michal},
  title =	{{Simultaneous Tracking of Multiple Objects Using Fast Level Set-Like Algorithm}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{69--76},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.69},
  URN =		{urn:nbn:de:0030-drops-30625},
  doi =		{10.4230/OASIcs.MEMICS.2010.69},
  annote =	{Keywords: level set framework, topology preservation, object tracking}
}
Document
GPU-Based Sample-Parallel Context Modeling for EBCOT in JPEG2000

Authors: Jiri Matela, Vit Rusnak, and Petr Holub


Abstract
Embedded Block Coding with Optimal Truncation (EBCOT) is the fundamental and computationally very demanding part of the compression process of JPEG2000 image compression standard. EBCOT itself consists of two tiers. In Tier-1, image samples are compressed using context modeling and arithmetic coding. Resulting bit-stream is further formated and truncated in Tier-2. JPEG2000 has a number of applications in various fields where the processing speed and/or latency is a crucial attribute and the main limitation with state of the art implementations. In this paper we propose a new parallel approach to EBCOT context modeling that truly exploits massively parallel capabilities of modern GPUs and enables concurrent processing of individual image samples. Performance evaluation of our prototype shows speedup 12 times for the context modeller, and 1.4­5.3 times for the whole EBCOT Tier-1, which includes not yet optimized arithmetic coder.

Cite as

Jiri Matela, Vit Rusnak, and Petr Holub. GPU-Based Sample-Parallel Context Modeling for EBCOT in JPEG2000. 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. 77-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{matela_et_al:OASIcs.MEMICS.2010.77,
  author =	{Matela, Jiri and Rusnak, Vit and Holub, Petr},
  title =	{{GPU-Based Sample-Parallel Context Modeling for EBCOT in JPEG2000}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{77--84},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.77},
  URN =		{urn:nbn:de:0030-drops-30681},
  doi =		{10.4230/OASIcs.MEMICS.2010.77},
  annote =	{Keywords: JPEG2000, EBCOT, Context Modeling, GPU, GPGPU, parallel}
}
Document
Hijacking the Linux Kernel

Authors: Boris Prochazka, Tomas Vojnar, and Martin Drahansky


Abstract
In this paper, a new method of hijacking the Linux kernel is presented. It is based on analysing the Linux system call handler, where a proper set of instructions is subsequently replaced by a jump to a different function. The ability to change the execution flow in the middle of an existing function represents a unique approach in Linux kernel hacking. The attack is applicable to all kernels from the 2.6 series on the Intel architecture. Due to this, rootkits based on this kind of technique represent a high risk for Linux administrators.

Cite as

Boris Prochazka, Tomas Vojnar, and Martin Drahansky. Hijacking the Linux Kernel. 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. 85-92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{prochazka_et_al:OASIcs.MEMICS.2010.85,
  author =	{Prochazka, Boris and Vojnar, Tomas and Drahansky, Martin},
  title =	{{Hijacking the Linux Kernel}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{85--92},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.85},
  URN =		{urn:nbn:de:0030-drops-30635},
  doi =		{10.4230/OASIcs.MEMICS.2010.85},
  annote =	{Keywords: Linux kernel hacking, rootkit}
}
Document
Fast Translated Simulation of ASIPs

Authors: Zdenek Prikryl, Jakub Kroustek, Tomas Hruska, and Dusan Kolar


Abstract
Application-specific instruction set processors are the core of nowadays embedded systems. Therefore, the designers need to have powerful tools for the processor design. The tools should be generated automatically based on a processor description. One of the most important tools is the simulator. It is used during a testing phase of the processor design and during target software development. The key feature of the simulator is its speed. The concept of a special simulation type ­ translated simulation ­ is presented in this paper. This simulation exploits information from a target C compiler. Both the simulator and the C compiler are generated based on the processor description in an architecture description language ISAC. Experimental results of this concept show very good simulation speed and fast generation of the simulator.

Cite as

Zdenek Prikryl, Jakub Kroustek, Tomas Hruska, and Dusan Kolar. Fast Translated Simulation of ASIPs. 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. 93-100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{prikryl_et_al:OASIcs.MEMICS.2010.93,
  author =	{Prikryl, Zdenek and Kroustek, Jakub and Hruska, Tomas and Kolar, Dusan},
  title =	{{Fast Translated Simulation of ASIPs}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{93--100},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.93},
  URN =		{urn:nbn:de:0030-drops-30608},
  doi =		{10.4230/OASIcs.MEMICS.2010.93},
  annote =	{Keywords: Hardware/sofware co-design, simulation, architecture description languages, application-specific instruction set processors}
}
Document
Test-Case Generation for Embedded Binary Code Using Abstract Interpretation

Authors: Thomas Reinbacher, Jörg Brauer, Martin Horauer, Andreas Steininger, and Stefan Kowalewski


Abstract
This paper describes a framework for test-case generation for microcontroller binary programs using abstract interpretation techniques. The key idea of our approach is to derive program invariants a priori, and then use backward analysis to obtain test vectors that are executed on the target microcontroller. Due to the structure of binary code, the abstract interpretation framework is based on propositional encodings of the program semantics and SAT solving.

Cite as

Thomas Reinbacher, Jörg Brauer, Martin Horauer, Andreas Steininger, and Stefan Kowalewski. Test-Case Generation for Embedded Binary Code Using Abstract Interpretation. 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. 101-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{reinbacher_et_al:OASIcs.MEMICS.2010.101,
  author =	{Reinbacher, Thomas and Brauer, J\"{o}rg and Horauer, Martin and Steininger, Andreas and Kowalewski, Stefan},
  title =	{{Test-Case Generation for Embedded Binary Code Using Abstract Interpretation}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{101--108},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.101},
  URN =		{urn:nbn:de:0030-drops-30586},
  doi =		{10.4230/OASIcs.MEMICS.2010.101},
  annote =	{Keywords: Test-Case Generation, Embedded Binary Code, Abstract Interpretation}
}
Document
Instructor Selector Generation from Architecture Description

Authors: Miloslav Trmac, Adam Husar, Jan Hranac, Tomas Hruska, and Karel Masarik


Abstract
We describe an automated way to generate data for a practical LLVM instruction selector based on machine-generated description of the target architecture at register transfer level. The generated instruction selector can handle arbitrarily complex machine instructions with no internal control flow, and can automatically find and take advantage of arithmetic properties of an instructions, specialized pseudo-registers and special cases of immediate operands.

Cite as

Miloslav Trmac, Adam Husar, Jan Hranac, Tomas Hruska, and Karel Masarik. Instructor Selector Generation from Architecture Description. 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. 109-115, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{trmac_et_al:OASIcs.MEMICS.2010.109,
  author =	{Trmac, Miloslav and Husar, Adam and Hranac, Jan and Hruska, Tomas and Masarik, Karel},
  title =	{{Instructor Selector Generation from Architecture Description}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{109--115},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.109},
  URN =		{urn:nbn:de:0030-drops-30616},
  doi =		{10.4230/OASIcs.MEMICS.2010.109},
  annote =	{Keywords: LLVM, instruction generator}
}
Document
Integer Programming for Media Streams Planning Problem

Authors: Pavel Troubil and Hana Rudova


Abstract
Continually increasing demands for high-quality videoconferencing have brought a problem of fully automated environment setup. A media streams planning problem forms an important part of this issue. As the multimedia streams are extremely bandwidth-demanding, their transmission has to be planned with respect to available capacities of network links and the plan also needs to be optimal in terms of data transfer latencies. This paper presents an integer programming solution of the problem and its implementation. The implementation achieved very promising results in performance-evaluating measurements. Compared to previous constraint-based solver, it is capable of finding optimal solution significantly faster, allowing for real-time planning of larger problem instances.

Cite as

Pavel Troubil and Hana Rudova. Integer Programming for Media Streams Planning Problem. 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. 116-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{troubil_et_al:OASIcs.MEMICS.2010.116,
  author =	{Troubil, Pavel and Rudova, Hana},
  title =	{{Integer Programming for Media Streams Planning Problem}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{116--123},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.116},
  URN =		{urn:nbn:de:0030-drops-30661},
  doi =		{10.4230/OASIcs.MEMICS.2010.116},
  annote =	{Keywords: Media streams planning, integer programming}
}
Document
Monitoring and Control of Temperature in Networks-on-Chip

Authors: Tim Wegner, Claas Cornelius, Andreas Tockhorn, and Dirk Timmermann


Abstract
Increasing integration densities and the emergence of nanotechnology cause issues related to reliability and power consumption to become dominant factors for the design of modern multi-core systems. Since the arising problems are enforced by high circuit temperatures, monitoring and control of on-chip temperature profiles need to be considered during design phase as well as during system operation. Hence, in this paper different approaches for the realization and integration of a monitoring system for temperature in multi-core systems based on Networks-on-Chip (NoCs) in combination with Dynamic Frequency Scaling (DFS) are investigated. Results show that both combinations using event-driven and time-driven forwarding more than double overall execution time and considerably reduce throughput of application data. Regarding performance of notification and reaction to temperature development event-driven forwarding clearly outperforms time-driven forwarding.

Cite as

Tim Wegner, Claas Cornelius, Andreas Tockhorn, and Dirk Timmermann. Monitoring and Control of Temperature in Networks-on-Chip. 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. 124-131, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{wegner_et_al:OASIcs.MEMICS.2010.124,
  author =	{Wegner, Tim and Cornelius, Claas and Tockhorn, Andreas and Timmermann, Dirk},
  title =	{{Monitoring and Control of Temperature in Networks-on-Chip}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{124--131},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.124},
  URN =		{urn:nbn:de:0030-drops-30735},
  doi =		{10.4230/OASIcs.MEMICS.2010.124},
  annote =	{Keywords: Network-on-Chip, Reliability, Monitoring, Temperature, Control}
}

Filters


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