1 Search Results for "Villevalois, Didier"


Document
Track B: Automata, Logic, Semantics, and Theory of Programming
Sequentiality of String-to-Context Transducers (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Pierre-Alain Reynier and Didier Villevalois

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
Transducers extend finite state automata with outputs, and describe transformations from strings to strings. Sequential transducers, which have a deterministic behaviour regarding their input, are of particular interest. However, unlike finite-state automata, not every transducer can be made sequential. The seminal work of Choffrut allows to characterise, amongst the functional one-way transducers, the ones that admit an equivalent sequential transducer. In this work, we extend the results of Choffrut to the class of transducers that produce their output string by adding simultaneously, at each transition, a string on the left and a string on the right of the string produced so far. We call them the string-to-context transducers. We obtain a multiple characterisation of the functional string-to-context transducers admitting an equivalent sequential one, based on a Lipschitz property of the function realised by the transducer, and on a pattern (a new twinning property). Last, we prove that given a string-to-context transducer, determining whether there exists an equivalent sequential one is in coNP.

Cite as

Pierre-Alain Reynier and Didier Villevalois. Sequentiality of String-to-Context Transducers (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 128:1-128:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{reynier_et_al:LIPIcs.ICALP.2019.128,
  author =	{Reynier, Pierre-Alain and Villevalois, Didier},
  title =	{{Sequentiality of String-to-Context Transducers}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{128:1--128:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.128},
  URN =		{urn:nbn:de:0030-drops-107042},
  doi =		{10.4230/LIPIcs.ICALP.2019.128},
  annote =	{Keywords: Transducers, Sequentiality, Twinning Property, Two-Way Transducers}
}
  • Refine by Author
  • 1 Reynier, Pierre-Alain
  • 1 Villevalois, Didier

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

  • Refine by Keyword
  • 1 Sequentiality
  • 1 Transducers
  • 1 Twinning Property
  • 1 Two-Way Transducers

  • Refine by Type
  • 1 document

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