Closure properties and decision problems of dag automata

Siva Anantharaman; Paliath Narendran; Michael Rusinowitch

doi:10.1016/j.ipl.2005.02.004

Closure properties and decision problems of dag automata

Siva Anantharaman
, Paliath Narendran
, Michael Rusinowitch

Computer Science

University at Albany

Université d'Orléans
LORIA-INRIA Lorraine

Research output: Contribution to journal › Article › peer-review

25 Scopus citations

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.

Original language	English
Pages (from-to)	231-240
Number of pages	10
Journal	Information Processing Letters
Volume	94
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2005.02.004
State	Published - Jun 15 2005

Keywords

Complementation
Determinism
Emptiness problem
Formal languages
Tree automata
Universality problem

Access to Document

10.1016/j.ipl.2005.02.004

Cite this

@article{da3b1ef5dd2349e0b432940cad982570,

title = "Closure properties and decision problems of dag automata",

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.",

keywords = "Complementation, Determinism, Emptiness problem, Formal languages, Tree automata, Universality problem",

author = "Siva Anantharaman and Paliath Narendran and Michael Rusinowitch",

year = "2005",

month = jun,

day = "15",

doi = "10.1016/j.ipl.2005.02.004",

language = "English",

volume = "94",

pages = "231--240",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Closure properties and decision problems of dag automata

AU - Anantharaman, Siva

AU - Narendran, Paliath

AU - Rusinowitch, Michael

PY - 2005/6/15

Y1 - 2005/6/15

N2 - 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.

AB - 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.

KW - Complementation

KW - Determinism

KW - Emptiness problem

KW - Formal languages

KW - Tree automata

KW - Universality problem

UR - https://www.scopus.com/pages/publications/18444377894

U2 - 10.1016/j.ipl.2005.02.004

DO - 10.1016/j.ipl.2005.02.004

M3 - Article

SN - 0020-0190

VL - 94

SP - 231

EP - 240

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Closure properties and decision problems of dag automata

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this