License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.142
URN: urn:nbn:de:0030-drops-91463
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9146/
Go to the corresponding LIPIcs Volume Portal

Winter, Sarah

Uniformization Problems for Synchronizations of Automatic Relations on Words

pdf-format:
LIPIcs-ICALP-2018-142.pdf (0.5 MB)

Abstract

A uniformization of a binary relation is a function that is contained in the relation and has the same domain as the relation. The synthesis problem asks for effective uniformization for classes of relations and functions that can be implemented in a specific way.
We consider the synthesis problem for automatic relations over finite words (also called regular or synchronized rational relations) by functions implemented by specific classes of sequential transducers.
It is known that the problem "Given an automatic relation, does it have a uniformization by a subsequential transducer?" is decidable in the two variants where the uniformization can either be implemented by an arbitrary subsequential transducer or it has to be implemented by a synchronous transducer. We introduce a new variant of this problem in which the allowed input/output behavior of the subsequential transducer is specified by a set of synchronizations and prove decidability for a specific class of synchronizations.

BibTeX - Entry

@InProceedings{winter:LIPIcs:2018:9146,
  author =	{Sarah Winter},
  title =	{{Uniformization Problems for Synchronizations of Automatic Relations on Words}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{142:1--142:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9146},
  URN =		{urn:nbn:de:0030-drops-91463},
  doi =		{10.4230/LIPIcs.ICALP.2018.142},
  annote =	{Keywords: automatic relation, uniformization, synchronization, transducer}
}

Keywords: automatic relation, uniformization, synchronization, transducer
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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