HAL - INRIA :: [inria-00271646, version 1] Path-equivalent developments in acyclic weighted automata

inria-00271646, version 1

Path-equivalent developments in acyclic weighted automata

Mathieu Giraud ( Author to contact preferably )^a^, 1, 2, Philippe Veber^b^, 3, Dominique Lavenier ()^a^, 3

International Journal of Foundations of Computer Science 18, 4 (2007) 799-812

Abstract: Weighted ﬁnite automata (WFA) are used with FPGA accelerating hardware to scan large genomic banks. Hardwiring such automata raises surface area and clock frequency constraints, requiring eﬃcient ε-transitions-removal techniques. In this paper, we present bounds on the number of new transitions for the development of acyclic WFA, which is a special case of the ε-transitions-removal problem. We introduce a new problem, a partial removal of ε-transitions while accepting short chains of ε-transitions.

a – CNRS
b – INRIA
1: Laboratoire d'Informatique Fondamentale de Lille (LIFL)
CNRS : UMR8022 – INRIA – IRCICA – Université des Sciences et Technologies de Lille - Lille I
2: SEQUOIA (INRIA Lille - Nord Europe)
INRIA – CNRS : UMR8022 – Université des Sciences et Technologies de Lille - Lille I – Université Charles de Gaulle - Lille III
3: SYMBIOSE (INRIA - IRISA)
CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1

inria-00271646, version 1
http://hal.inria.fr/inria-00271646
oai:hal.inria.fr:inria-00271646
From: Mathieu Giraud <>
Submitted on: Wednesday, 9 April 2008 18:11:56
Updated on: Wednesday, 9 April 2008 20:58:53

See detailed view

Associated documents

PDF :

DOI: 10.1142/S012905410700498X

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles in peer-reviewed journal</head>
<biblStruct type="article" xml:id="inria-00271646"><analytic>
<author><persName><forename>Mathieu</forename><surname>Giraud</surname></persName>
<affiliation>
<orgName type="laboratory">LIFL</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale de Lille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">IRCICA</orgName>
<orgName type="institution">Université des Sciences et Technologies de Lille - Lille I</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</orgName>
<orgName type="team">SEQUOIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université des Sciences et Technologies de Lille - Lille I</orgName>
<orgName type="institution">Université Charles de Gaulle - Lille III</orgName>
</affiliation>
</author>
<author><persName><forename>Philippe</forename><surname>Veber</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">SYMBIOSE</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">INSA Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Dominique</forename><surname>Lavenier</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">SYMBIOSE</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">INSA Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<title type="main" level="a">Path-equivalent developments in acyclic weighted automata</title></analytic><monogr><title level="j" type="main">International Journal of Foundations of Computer Science</title><imprint><publisher>World Scientific</publisher><biblScope type="publicationDate">2007-00-00</biblScope><biblScope type="vol">18</biblScope><biblScope type="issue">4</biblScope><biblScope type="pp">799-812</biblScope></imprint></monogr><idno type="doi">10.1142/S012905410700498X</idno><idno type="HALid">http://hal.inria.fr/inria-00271646</idno><idno type="HALFile">http://hal.inria.fr/inria-00271646/PDF/gvl-ijfcs-07-preprint.pdf</idno></biblStruct>
</listBibl>
</listBibl>