License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.11.10.57
URN: urn:nbn:de:0030-drops-159282
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15928/
Go back to Dagstuhl Reports

Colcombet, Thomas ; Quaas, Karin ; Skrzypczak, Michał
Weitere Beteiligte (Hrsg. etc.): Thomas Colcombet and Karin Quaas and Michał Skrzypczak

Unambiguity in Automata Theory (Dagstuhl Seminar 21452)

pdf-format:
dagrep_v011_i010_p057_21452.pdf (3 MB)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 21452 "Unambiguity in Automata Theory". The aim of the seminar was to improve the understanding of the notion of unambiguity in automata theory, especially with respect to questions related to the expressive power, succinctness, and the tractability of unambiguous devices. The main motivation behind these studies is the hope that unambiguous machines can provide a golden balance between efficiency - sometimes not worse than for deterministic devices - and expressibility / succinctness, which often is similar to the general nondeterministic machines. These trade-offs become especially important in the models where the expressiveness or the decidability status of unambiguous machines is different from that of nondeterministic ones, as it is the case, e.g., for register automata.

BibTeX - Entry

@Article{colcombet_et_al:DagRep.11.10.57,
  author =	{Colcombet, Thomas and Quaas, Karin and Skrzypczak, Micha{\l}},
  title =	{{Unambiguity in Automata Theory (Dagstuhl Seminar 21452)}},
  pages =	{57--71},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{10},
  editor =	{Colcombet, Thomas and Quaas, Karin and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15928},
  URN =		{urn:nbn:de:0030-drops-159282},
  doi =		{10.4230/DagRep.11.10.57},
  annote =	{Keywords: Unambiguity in Automata Theory, Dagstuhl Seminar}
}

Keywords: Unambiguity in Automata Theory, Dagstuhl Seminar
Collection: DagRep, Volume 11, Issue 10
Issue Date: 2022
Date of publication: 11.04.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI