A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay

Sabrina Mantaci, Carla Selmi, Laura Giambruno, Jean Néraud

Risultato della ricerca: Chapter

Abstract

In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers associated to different keys have an isomorphic non trivial strongly connected component.
Lingua originaleEnglish
Titolo della pubblicazione ospiteDevelopments in Language Theory, Lecture Notes in Computer Science Volume 7410
Pagine471-476
Numero di pagine6
Stato di pubblicazionePublished - 2012

Serie di pubblicazioni

NomeLECTURE NOTES IN COMPUTER SCIENCE

Fingerprint

Decoding
Transducers
Transducer
Isomorphic
Generalise
Prefix
Connected Components
Trivial
Encoding
Generalization
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Mantaci, S., Selmi, C., Giambruno, L., & Néraud, J. (2012). A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay. In Developments in Language Theory, Lecture Notes in Computer Science Volume 7410 (pagg. 471-476). (LECTURE NOTES IN COMPUTER SCIENCE).

A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay. / Mantaci, Sabrina; Selmi, Carla; Giambruno, Laura; Néraud, Jean.

Developments in Language Theory, Lecture Notes in Computer Science Volume 7410. 2012. pag. 471-476 (LECTURE NOTES IN COMPUTER SCIENCE).

Risultato della ricerca: Chapter

Mantaci, S, Selmi, C, Giambruno, L & Néraud, J 2012, A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay. in Developments in Language Theory, Lecture Notes in Computer Science Volume 7410. LECTURE NOTES IN COMPUTER SCIENCE, pagg. 471-476.
Mantaci S, Selmi C, Giambruno L, Néraud J. A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay. In Developments in Language Theory, Lecture Notes in Computer Science Volume 7410. 2012. pag. 471-476. (LECTURE NOTES IN COMPUTER SCIENCE).
Mantaci, Sabrina ; Selmi, Carla ; Giambruno, Laura ; Néraud, Jean. / A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay. Developments in Language Theory, Lecture Notes in Computer Science Volume 7410. 2012. pagg. 471-476 (LECTURE NOTES IN COMPUTER SCIENCE).
@inbook{3e51dab2770049ab8efdf07aa76e392b,
title = "A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay",
abstract = "In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers associated to different keys have an isomorphic non trivial strongly connected component.",
author = "Sabrina Mantaci and Carla Selmi and Laura Giambruno and Jean N{\'e}raud",
year = "2012",
language = "English",
isbn = "978-3-642-31652-4",
series = "LECTURE NOTES IN COMPUTER SCIENCE",
pages = "471--476",
booktitle = "Developments in Language Theory, Lecture Notes in Computer Science Volume 7410",

}

TY - CHAP

T1 - A Generalization of Girod’s Bidirectional Decoding Method to Codes with a Finite Deciphering Delay

AU - Mantaci, Sabrina

AU - Selmi, Carla

AU - Giambruno, Laura

AU - Néraud, Jean

PY - 2012

Y1 - 2012

N2 - In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers associated to different keys have an isomorphic non trivial strongly connected component.

AB - In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers associated to different keys have an isomorphic non trivial strongly connected component.

UR - http://hdl.handle.net/10447/103125

UR - http://link.springer.com/chapter/10.1007%2F978-3-642-31653-1_43

M3 - Chapter

SN - 978-3-642-31652-4

T3 - LECTURE NOTES IN COMPUTER SCIENCE

SP - 471

EP - 476

BT - Developments in Language Theory, Lecture Notes in Computer Science Volume 7410

ER -