2 Search Results for "Reis, Gerd"

Document
DOI: 10.4230/LIPIcs.STACS.2026.48
Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata

Authors: Bruno Guillon, Luca Prigioniero, and Javad Taheri

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We prove that, paying a polynomial increase in size only, every unrestricted two-way nondeterministic finite automaton (2NFA) can be complemented by a 1-limited automaton (1-LA), a nondeterministic extension of 2NFAs still characterizing regular languages. The resulting machine is actually a restricted form of 1-LAs - known as 2NFAs with common guess - and is self-verifying. A corollary of our construction is that a single exponential is necessary and sufficient for complementing 1-LAs.
Cite as

Bruno Guillon, Luca Prigioniero, and Javad Taheri. Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{guillon_et_al:LIPIcs.STACS.2026.48,
  author =	{Guillon, Bruno and Prigioniero, Luca and Taheri, Javad},
  title =	{{Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.48},
  URN =		{urn:nbn:de:0030-drops-255378},
  doi =		{10.4230/LIPIcs.STACS.2026.48},
  annote =	{Keywords: descriptional complexity, inductive counting, common-guess}
}
Document
DOI: 10.4230/OASIcs.VLUDS.2011.89
Texture-based Tracking in mm-wave Images

Authors: Peter Salz, Gerd Reis, and Didier Stricker

Published in: OASIcs, Volume 27, Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011

Abstract
Current tracking methods rely on color-, intensity-, and edge-based features to compute a description of an image region. These approaches are not well-suited for low-quality images such as mm-wave data from full-body scanners. In order to perform tracking in such challenging grayscale images, we propose several enhancements and extensions to the Visual Tracking Decomposition (VTD) by Kwon and Lee. A novel region descriptor, which uses texture-based features, is presented and integrated into VTD. We improve VTD by adding a sophisticated weighting scheme for observations, better motion models, and a more realistic way for sampling and interaction. Our method not only outperforms VTD on mm-wave data but also has comparable results on normal-quality images. We are confident that our region descriptor can easily be extended to other kinds of features and applications such that tracking can be performed in a large variety of image data, especially low-resolution, low-illumination and noisy images.
Cite as

Peter Salz, Gerd Reis, and Didier Stricker. Texture-based Tracking in mm-wave Images. In Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011. Open Access Series in Informatics (OASIcs), Volume 27, pp. 89-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{salz_et_al:OASIcs.VLUDS.2011.89,
  author =	{Salz, Peter and Reis, Gerd and Stricker, Didier},
  title =	{{Texture-based Tracking in mm-wave Images}},
  booktitle =	{Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011},
  pages =	{89--101},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-46-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{27},
  editor =	{Garth, Christoph and Middel, Ariane and Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.VLUDS.2011.89},
  URN =		{urn:nbn:de:0030-drops-37437},
  doi =		{10.4230/OASIcs.VLUDS.2011.89},
  annote =	{Keywords: Visual Tracking decomposition, low-quality images, texture features, mm-wave imagery}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2012

  • Refine by Author
  • 1 Guillon, Bruno
  • 1 Prigioniero, Luca
  • 1 Reis, Gerd
  • 1 Salz, Peter
  • 1 Stricker, Didier
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Theory of computation → Formal languages and automata theory
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Regular languages

  • Refine by Keyword
  • 1 Visual Tracking decomposition
  • 1 common-guess
  • 1 descriptional complexity
  • 1 inductive counting
  • 1 low-quality images
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact