DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.70

Differential Tree Automata

Authors: Rida Ait El Manssour, Vincent Cheval, Mahsa Shirmohammadi, and James Worrell

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract

In this paper we introduce the notion of a differential tree automaton. Differential tree automata generalise weighted tree automata (over a field) by allowing the transition weights to be rational functions of the tree size. Whereas the class of generating functions of weighted tree automata coincides with the class of algebraic power series, our main result is that the class of generating functions of differential tree automata coincides with the class of differentially algebraic power series. As a corollary, we obtain a decision procedure for determining equivalence of differential tree automata. In the course of proving our main result we identify a class of recurrences that characterises the sequence of coefficients of a differentially algebraic power series, generalising Reutenauer’s matrix representation of polynomially recursive sequences. We further identify a natural syntactic subset of differential tree automata whose generating functions are given by rational dynamical systems, that is, as components of the solution of a system of differential equations y' = F(y), where F is a vector of rational functions that is defined at y(0). We further show that this class of power series can be characterised in terms of the classical notion of weighted tree automata by using a labelled generating function on trees.

Cite as

Rida Ait El Manssour, Vincent Cheval, Mahsa Shirmohammadi, and James Worrell. Differential Tree Automata. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 70:1-70:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aitelmanssour_et_al:LIPIcs.LICS.2026.70,
  author =	{Ait El Manssour, Rida and Cheval, Vincent and Shirmohammadi, Mahsa and Worrell, James},
  title =	{{Differential Tree Automata}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{70:1--70:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.70},
  URN =		{urn:nbn:de:0030-drops-268570},
  doi =		{10.4230/LIPIcs.LICS.2026.70},
  annote =	{Keywords: Combinatorial species, Differentially algebraic series, Weighted automata}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2015.575

Secure Refinements of Communication Channels

Authors: Vincent Cheval, Véronique Cortier, and Eric le Morvan

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract

It is a common practice to design a protocol (say Q) assuming some secure channels. Then the secure channels are implemented using any standard protocol, e.g. TLS. In this paper, we study when such a practice is indeed secure. We provide a characterization of both confidential and authenticated channels. As an application, we study several protocols of the literature including TLS and BAC protocols. Thanks to our result, we can consider a larger number of sessions when analyzing complex protocols resulting from explicit implementation of the secure channels of some more abstract protocol Q.

Cite as

Vincent Cheval, Véronique Cortier, and Eric le Morvan. Secure Refinements of Communication Channels. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 575-589, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cheval_et_al:LIPIcs.FSTTCS.2015.575,
  author =	{Cheval, Vincent and Cortier, V\'{e}ronique and le Morvan, Eric},
  title =	{{Secure Refinements of Communication Channels}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{575--589},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.575},
  URN =		{urn:nbn:de:0030-drops-56583},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.575},
  annote =	{Keywords: Protocol, Composition, Formal methods, Channels, Implementation}
}

Search Results

Documents authored by Cheval, Vincent

Differential Tree Automata

Abstract

Cite as

Secure Refinements of Communication Channels

Abstract

Cite as

Thanks for your feedback!

Could not send message