How Useful are Dag Automata?
Identifieur interne : 002829 ( Hal/Corpus ); précédent : 002828; suivant : 002830How Useful are Dag Automata?
Auteurs : Siva Anantharaman ; Paliath Narendran ; Michaël RusinowitchSource :
English descriptors
- mix :
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.
Url:
Links to Exploration step
Hal:hal-00077510Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">How Useful are Dag Automata?</title>
<author><name sortKey="Anantharaman, Siva" sort="Anantharaman, Siva" uniqKey="Anantharaman S" first="Siva" last="Anantharaman">Siva Anantharaman</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-1625" status="OLD"><orgName>Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<orgName type="acronym">LIFO</orgName>
<desc><address><addrLine>Batiment IIIA 6 Rue Léonard de Vinci - BP 6759 45067 ORLEANS CEDEX 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/lifo/</ref>
</desc>
<listRelation><relation name="EA4022" active="#struct-300297" type="direct"></relation>
<relation active="#struct-300379" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="EA4022" active="#struct-300297" type="direct"><org type="institution" xml:id="struct-300297" status="VALID"><idno type="IdRef">026402971</idno>
<idno type="ISNI">0000000121581666 </idno>
<orgName>Université d'Orléans</orgName>
<orgName type="acronym">UO</orgName>
<desc><address><addrLine>Château de la Source - Avenue du Parc Floral - BP 6749 - 45067 Orléans cedex 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300379" type="direct"><org type="institution" xml:id="struct-300379" status="VALID"><orgName>Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Narendran, Paliath" sort="Narendran, Paliath" uniqKey="Narendran P" first="Paliath" last="Narendran">Paliath Narendran</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-1625" status="OLD"><orgName>Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<orgName type="acronym">LIFO</orgName>
<desc><address><addrLine>Batiment IIIA 6 Rue Léonard de Vinci - BP 6759 45067 ORLEANS CEDEX 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/lifo/</ref>
</desc>
<listRelation><relation name="EA4022" active="#struct-300297" type="direct"></relation>
<relation active="#struct-300379" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="EA4022" active="#struct-300297" type="direct"><org type="institution" xml:id="struct-300297" status="VALID"><idno type="IdRef">026402971</idno>
<idno type="ISNI">0000000121581666 </idno>
<orgName>Université d'Orléans</orgName>
<orgName type="acronym">UO</orgName>
<desc><address><addrLine>Château de la Source - Avenue du Parc Floral - BP 6749 - 45067 Orléans cedex 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300379" type="direct"><org type="institution" xml:id="struct-300379" status="VALID"><orgName>Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michaël" last="Rusinowitch">Michaël Rusinowitch</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-1625" status="OLD"><orgName>Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<orgName type="acronym">LIFO</orgName>
<desc><address><addrLine>Batiment IIIA 6 Rue Léonard de Vinci - BP 6759 45067 ORLEANS CEDEX 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/lifo/</ref>
</desc>
<listRelation><relation name="EA4022" active="#struct-300297" type="direct"></relation>
<relation active="#struct-300379" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="EA4022" active="#struct-300297" type="direct"><org type="institution" xml:id="struct-300297" status="VALID"><idno type="IdRef">026402971</idno>
<idno type="ISNI">0000000121581666 </idno>
<orgName>Université d'Orléans</orgName>
<orgName type="acronym">UO</orgName>
<desc><address><addrLine>Château de la Source - Avenue du Parc Floral - BP 6749 - 45067 Orléans cedex 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300379" type="direct"><org type="institution" xml:id="struct-300379" status="VALID"><orgName>Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00077510</idno>
<idno type="halId">hal-00077510</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00077510</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00077510</idno>
<date when="2004">2004</date>
<idno type="wicri:Area/Hal/Corpus">002829</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">How Useful are Dag Automata?</title>
<author><name sortKey="Anantharaman, Siva" sort="Anantharaman, Siva" uniqKey="Anantharaman S" first="Siva" last="Anantharaman">Siva Anantharaman</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-1625" status="OLD"><orgName>Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<orgName type="acronym">LIFO</orgName>
<desc><address><addrLine>Batiment IIIA 6 Rue Léonard de Vinci - BP 6759 45067 ORLEANS CEDEX 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/lifo/</ref>
</desc>
<listRelation><relation name="EA4022" active="#struct-300297" type="direct"></relation>
<relation active="#struct-300379" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="EA4022" active="#struct-300297" type="direct"><org type="institution" xml:id="struct-300297" status="VALID"><idno type="IdRef">026402971</idno>
<idno type="ISNI">0000000121581666 </idno>
<orgName>Université d'Orléans</orgName>
<orgName type="acronym">UO</orgName>
<desc><address><addrLine>Château de la Source - Avenue du Parc Floral - BP 6749 - 45067 Orléans cedex 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300379" type="direct"><org type="institution" xml:id="struct-300379" status="VALID"><orgName>Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Narendran, Paliath" sort="Narendran, Paliath" uniqKey="Narendran P" first="Paliath" last="Narendran">Paliath Narendran</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-1625" status="OLD"><orgName>Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<orgName type="acronym">LIFO</orgName>
<desc><address><addrLine>Batiment IIIA 6 Rue Léonard de Vinci - BP 6759 45067 ORLEANS CEDEX 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/lifo/</ref>
</desc>
<listRelation><relation name="EA4022" active="#struct-300297" type="direct"></relation>
<relation active="#struct-300379" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="EA4022" active="#struct-300297" type="direct"><org type="institution" xml:id="struct-300297" status="VALID"><idno type="IdRef">026402971</idno>
<idno type="ISNI">0000000121581666 </idno>
<orgName>Université d'Orléans</orgName>
<orgName type="acronym">UO</orgName>
<desc><address><addrLine>Château de la Source - Avenue du Parc Floral - BP 6749 - 45067 Orléans cedex 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300379" type="direct"><org type="institution" xml:id="struct-300379" status="VALID"><orgName>Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michaël" last="Rusinowitch">Michaël Rusinowitch</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-1625" status="OLD"><orgName>Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<orgName type="acronym">LIFO</orgName>
<desc><address><addrLine>Batiment IIIA 6 Rue Léonard de Vinci - BP 6759 45067 ORLEANS CEDEX 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/lifo/</ref>
</desc>
<listRelation><relation name="EA4022" active="#struct-300297" type="direct"></relation>
<relation active="#struct-300379" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="EA4022" active="#struct-300297" type="direct"><org type="institution" xml:id="struct-300297" status="VALID"><idno type="IdRef">026402971</idno>
<idno type="ISNI">0000000121581666 </idno>
<orgName>Université d'Orléans</orgName>
<orgName type="acronym">UO</orgName>
<desc><address><addrLine>Château de la Source - Avenue du Parc Floral - BP 6749 - 45067 Orléans cedex 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-orleans.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300379" type="direct"><org type="institution" xml:id="struct-300379" status="VALID"><orgName>Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>E-Unification</term>
</keywords>
<keywords scheme="mix" xml:lang="it"><term>E-Unification.</term>
<term>complementation</term>
<term>complexity</term>
<term>decidability</term>
<term>determinism</term>
<term>labels</term>
<term>tree automata</term>
<term>universality</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">How Useful are Dag Automata?</title>
<author role="aut"><persName><forename type="first">Siva</forename>
<surname>Anantharaman</surname>
</persName>
<email>siva@univ-orleans.fr</email>
<idno type="halauthor">103679</idno>
<affiliation ref="#struct-1625"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Paliath</forename>
<surname>Narendran</surname>
</persName>
<email>dran@cs.albany.edu</email>
<idno type="halauthor">103680</idno>
<affiliation ref="#struct-1625"></affiliation>
<affiliation ref="#struct-15502"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Michaël</forename>
<surname>Rusinowitch</surname>
</persName>
<email>rusi@loria.fr</email>
<idno type="idhal">michael-rusinowitch</idno>
<idno type="halauthor">103719</idno>
<affiliation ref="#struct-1625"></affiliation>
<affiliation ref="#struct-2366"></affiliation>
</author>
<editor role="depositor"><persName><forename>Siva</forename>
<surname>Anantharaman</surname>
</persName>
<email>siva@univ-orleans.fr</email>
</editor>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2006-06-01 17:35:02</date>
<date type="whenModified">2016-05-19 01:12:06</date>
<date type="whenReleased">2006-06-01 18:47:42</date>
<date type="whenProduced">2004</date>
<date type="whenEndEmbargoed">2006-06-01</date>
<ref type="file" target="https://hal.archives-ouvertes.fr/hal-00077510/document"><date notBefore="2006-06-01"></date>
</ref>
<ref type="file" n="1" target="https://hal.archives-ouvertes.fr/hal-00077510/file/RR2004-12.pdf"><date notBefore="2006-06-01"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="111190"><persName><forename>Siva</forename>
<surname>Anantharaman</surname>
</persName>
<email>siva@univ-orleans.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">hal-00077510</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00077510</idno>
<idno type="halBibtex">anantharaman:hal-00077510</idno>
<idno type="halRefHtml">Projet PRV (du LIFO). Rapport de Recherche (LIFO). 2004</idno>
<idno type="halRef">Projet PRV (du LIFO). Rapport de Recherche (LIFO). 2004</idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="UNIV-FCOMTE">Université de Franche-Comté</idno>
<idno type="stamp" n="UNIV-ORLEANS">Université d'Orléans</idno>
<idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno>
<idno type="stamp" n="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA-FM" p="LORIA">Méthodes formelles</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="MSL">Modelisation Systemes Langages</idno>
<idno type="stamp" n="INRIA2">INRIA 2</idno>
<idno type="stamp" n="ENSI-BOURGES">Ecole Nationale Supérieure d'Ingénieurs de Bourges</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno>
<idno type="stamp" n="MSL-THESE">Modelisation Systemes Langages</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="UNIV-BM">Université de Technologie de Belfort-Montbeliard</idno>
<idno type="stamp" n="ENSMM">Ecole Nationale Supérieure de Mécanique et des Microtechniques</idno>
<idno type="stamp" n="FEMTO-ST" p="UNIV-FCOMTE">Franche-Comté Electronique, Mécanique, Thermique et Optique - Sciences et Technologies</idno>
<idno type="stamp" n="UNIV-BM-THESE">Université de Technologie de Belfort-Montbeliard</idno>
</seriesStmt>
<notesStmt><note type="commentary">25 pages</note>
<note type="description">Rapport de Recherche (LIFO)</note>
<note type="audience" n="0">Not set</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">How Useful are Dag Automata?</title>
<author role="aut"><persName><forename type="first">Siva</forename>
<surname>Anantharaman</surname>
</persName>
<email>siva@univ-orleans.fr</email>
<idno type="halAuthorId">103679</idno>
<affiliation ref="#struct-1625"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Paliath</forename>
<surname>Narendran</surname>
</persName>
<email>dran@cs.albany.edu</email>
<idno type="halAuthorId">103680</idno>
<affiliation ref="#struct-1625"></affiliation>
<affiliation ref="#struct-15502"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Michaël</forename>
<surname>Rusinowitch</surname>
</persName>
<email>rusi@loria.fr</email>
<idno type="idHal">michael-rusinowitch</idno>
<idno type="halAuthorId">103719</idno>
<affiliation ref="#struct-1625"></affiliation>
<affiliation ref="#struct-2366"></affiliation>
</author>
</analytic>
<monogr><idno type="localRef">Projet PRV (du LIFO)</idno>
<imprint><date type="datePub">2004</date>
</imprint>
</monogr>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="en">English</language>
</langUsage>
<textClass><keywords scheme="author"><term xml:lang="en">E-Unification</term>
<term xml:lang="it">tree automata</term>
<term xml:lang="it">labels</term>
<term xml:lang="it">determinism</term>
<term xml:lang="it">complementation</term>
<term xml:lang="it">universality</term>
<term xml:lang="it">decidability</term>
<term xml:lang="it">complexity</term>
<term xml:lang="it">E-Unification.</term>
</keywords>
<classCode scheme="halDomain" n="info.info-cl">Computer Science [cs]/Computation and Language [cs.CL]</classCode>
<classCode scheme="halTypology" n="OTHER">Other publications</classCode>
</textClass>
<abstract xml:lang="en">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.</abstract>
</profileDesc>
</hal>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002829 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 002829 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Hal |étape= Corpus |type= RBID |clé= Hal:hal-00077510 |texte= How Useful are Dag Automata? }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |