Closure properties and decision problems of dag automata
Identifieur interne : 006652 ( Main/Merge ); précédent : 006651; suivant : 006653Closure properties and decision problems of dag automata
Auteurs : Siva Anantharaman [France] ; Paliath Narendran [États-Unis] ; Michael Rusinowitch [France]Source :
- Information processing letters [ 0020-0190 ] ; 2005.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Tree automata are widely used in various contexts. They are closed under boolean operations and their emptiness problem is decidable in polynomial time. Dag automata are natural extensions of tree automata, operating on dags instead of on trees; they can also be used for solving problems. Our purpose in this paper is to show that algebraically they behave differently: the class of dag automata is not closed under complementation, dag automata are not determinizable, their membership problem is NP-complete, the universality problem is undecidable, and the emptiness problem is NP-complete even for deterministic labeled dag automata.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000575
- to stream PascalFrancis, to step Curation: 000463
- to stream PascalFrancis, to step Checkpoint: 000515
Links to Exploration step
Pascal:05-0215586Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Closure properties and decision problems of dag automata</title>
<author><name sortKey="Anantharaman, Siva" sort="Anantharaman, Siva" uniqKey="Anantharaman S" first="Siva" last="Anantharaman">Siva Anantharaman</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LIFO, Universlté d'Orléans</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>Universlté d'Orléans</wicri:noRegion>
<wicri:noRegion>LIFO, Universlté d'Orléans</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Narendran, Paliath" sort="Narendran, Paliath" uniqKey="Narendran P" first="Paliath" last="Narendran">Paliath Narendran</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>University at Albany, SUNY</s1>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>University at Albany, SUNY</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michael" last="Rusinowitch">Michael Rusinowitch</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>LORIA - Nancy</s1>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>LORIA - Nancy</wicri:noRegion>
<wicri:noRegion>LORIA - Nancy</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">05-0215586</idno>
<date when="2005">2005</date>
<idno type="stanalyst">PASCAL 05-0215586 INIST</idno>
<idno type="RBID">Pascal:05-0215586</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000575</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000463</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000515</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000515</idno>
<idno type="wicri:doubleKey">0020-0190:2005:Anantharaman S:closure:properties:and</idno>
<idno type="wicri:Area/Main/Merge">006652</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Closure properties and decision problems of dag automata</title>
<author><name sortKey="Anantharaman, Siva" sort="Anantharaman, Siva" uniqKey="Anantharaman S" first="Siva" last="Anantharaman">Siva Anantharaman</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LIFO, Universlté d'Orléans</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>Universlté d'Orléans</wicri:noRegion>
<wicri:noRegion>LIFO, Universlté d'Orléans</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Narendran, Paliath" sort="Narendran, Paliath" uniqKey="Narendran P" first="Paliath" last="Narendran">Paliath Narendran</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>University at Albany, SUNY</s1>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>University at Albany, SUNY</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michael" last="Rusinowitch">Michael Rusinowitch</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>LORIA - Nancy</s1>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>LORIA - Nancy</wicri:noRegion>
<wicri:noRegion>LORIA - Nancy</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Information processing letters</title>
<title level="j" type="abbreviated">Inf. process. lett.</title>
<idno type="ISSN">0020-0190</idno>
<imprint><date when="2005">2005</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Information processing letters</title>
<title level="j" type="abbreviated">Inf. process. lett.</title>
<idno type="ISSN">0020-0190</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm analysis</term>
<term>Complementation</term>
<term>Computer theory</term>
<term>Deterministic automaton</term>
<term>Formal language</term>
<term>Information processing</term>
<term>NP complete problem</term>
<term>Polynomial time</term>
<term>Problem solving</term>
<term>Tree automaton</term>
<term>Universality problem</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Automate arbre</term>
<term>Automate déterministe</term>
<term>Complémentation</term>
<term>Temps polynomial</term>
<term>Résolution problème</term>
<term>Problème NP complet</term>
<term>Langage formel</term>
<term>Informatique théorique</term>
<term>Traitement information</term>
<term>Analyse algorithme</term>
<term>05C05</term>
<term>68T20</term>
<term>46C07</term>
<term>Déterminisme</term>
<term>68Q45</term>
<term>Problème universalité</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Tree automata are widely used in various contexts. They are closed under boolean operations and their emptiness problem is decidable in polynomial time. Dag automata are natural extensions of tree automata, operating on dags instead of on trees; they can also be used for solving problems. Our purpose in this paper is to show that algebraically they behave differently: the class of dag automata is not closed under complementation, dag automata are not determinizable, their membership problem is NP-complete, the universality problem is undecidable, and the emptiness problem is NP-complete even for deterministic labeled dag automata.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
</list>
<tree><country name="France"><noRegion><name sortKey="Anantharaman, Siva" sort="Anantharaman, Siva" uniqKey="Anantharaman S" first="Siva" last="Anantharaman">Siva Anantharaman</name>
</noRegion>
<name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michael" last="Rusinowitch">Michael Rusinowitch</name>
</country>
<country name="États-Unis"><noRegion><name sortKey="Narendran, Paliath" sort="Narendran, Paliath" uniqKey="Narendran P" first="Paliath" last="Narendran">Paliath Narendran</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006652 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 006652 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Merge |type= RBID |clé= Pascal:05-0215586 |texte= Closure properties and decision problems of dag automata }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |