HAL - INRIA :: [inria-00178293, version 1] PATH-EQUIVALENT DEVELOPMENTS IN ACYCLIC WEIGHTED AUTOMATA

inria-00178293, version 1

PATH-EQUIVALENT DEVELOPMENTS IN ACYCLIC WEIGHTED AUTOMATA

Dominique Lavenier ()^a^, 1, Giraud Mathieu ², Verber Philippe^b^, 1

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

Abstract: Weighted finite automata (WFA) are used with FPGA accelerating hardware to scan large genomic banks. Hardwiring such automata raises surface area and clock frequency constraints, requiring efficient ∊-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: SYMBIOSE (INRIA - IRISA)
CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
2: Laboratoire d'Informatique Fondamentale de Lille (LIFL)
CNRS : UMR8022 – INRIA – IRCICA – Université des Sciences et Technologies de Lille - Lille I

inria-00178293, version 1
http://hal.inria.fr/inria-00178293
oai:hal.inria.fr:inria-00178293
From: Dominique Lavenier <>
Submitted on: Wednesday, 10 October 2007 16:10:06
Updated on: Monday, 19 October 2009 16:07:50

See detailed view

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-00178293"><analytic>
<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>
<author><persName><forename>Giraud</forename><surname>Mathieu</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>
</author>
<author><persName><forename>Verber</forename><surname>Philippe</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 (IJFCS)</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="HALid">http://hal.inria.fr/inria-00178293</idno></biblStruct>
</listBibl>
</listBibl>