How Useful are Dag Automata?

Siva Anantharaman; Paliath Narendran; Michaël Rusinowitch

hal-00077510, version 1

How Useful are Dag Automata?

Siva Anantharaman () ¹, Paliath Narendran () ^1, 2, Michaël Rusinowitch () ^1, 3

Rapport de Recherche (LIFO) (2004)

Abstract: Tree automata are widely used in various contexts; and their emptiness problem is known to be decidable in polynomial time. Dag automata -- with or without labels -- are natural extensions of tree automata, which can also be used for solving problems. Our purpose in this work is to show that algebraically they behave quite differently: the class of dag automata is not closed under complementation, dag automata are not determinizable, their membership problem turns out to be NP-complete, and universality is undecidable; and proving emptiness is NP-complete even for deterministic labeled dag automata.

1: Laboratoire d'Informatique Fondamentale d'Orléans (LIFO)
Université d'Orléans : EA4022 – Ecole Nationale Supérieure d'Ingénieurs de Bourges
2: Department of Computer Science [Albany] (CS)
State University of New York at Albany
3: CASSIS (INRIA Lorraine - LORIA / LIFC)
INRIA – CNRS : FRE2661 – Université de Franche-Comté – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

hal-00077510, version 1
http://hal.archives-ouvertes.fr/hal-00077510
oai:hal.archives-ouvertes.fr:hal-00077510
From: Siva Anantharaman <>
Submitted on: Thursday, 1 June 2006 17:35:02
Updated on: Wednesday, 17 January 2007 15:29:14

See detailed view

Associated documents

PDF :

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>Other publications</head>
<biblStruct type="article" xml:id="hal-00077510"><analytic>
<author><persName><forename>Siva</forename><surname>Anantharaman</surname></persName>
<affiliation>
<orgName type="laboratory">LIFO</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<country>FR</country>
<orgName type="institution">Université d'Orléans : EA4022</orgName>
<orgName type="institution">Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
</affiliation>
</author>
<author><persName><forename>Paliath</forename><surname>Narendran</surname></persName>
<affiliation>
<orgName type="laboratory">LIFO</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<country>FR</country>
<orgName type="institution">Université d'Orléans : EA4022</orgName>
<orgName type="institution">Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">CS</orgName>
<orgName type="team">Department of Computer Science [Albany]</orgName>
<country>US</country>
<orgName type="institution">State University of New York at Albany</orgName>
</affiliation>
</author>
<author><persName><forename>Michaël</forename><surname>Rusinowitch</surname></persName>
<affiliation>
<orgName type="laboratory">LIFO</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<country>FR</country>
<orgName type="institution">Université d'Orléans : EA4022</orgName>
<orgName type="institution">Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA / LIFC</orgName>
<orgName type="team">CASSIS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : FRE2661</orgName>
<orgName type="institution">Université de Franche-Comté</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">How Useful are Dag Automata?</title></analytic><monogr><imprint><biblScope type="publicationDate">2004-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00077510</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00077510/PDF/RR2004-12.pdf</idno></biblStruct>
</listBibl>
</listBibl>