Closure properties and decision problems of dag automata

DOI10.1016/j.ipl.2005.02.004zbMath1182.68099OpenAlexW1994475785MaRDI QIDQ1041757

Siva Anantharaman, Paliath Narendran, Michaël Rusinowitch

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.02.004

zbMATH Keywords

determinismcomplementationformal languagestree automataemptiness problemuniversality problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

Computational properties of partial non-deterministic matrices and their logics ⋮ The complexity of tree automata and XPath on grammar-compressed trees ⋮ An unexpected Boolean connective ⋮ Recognition of directed acyclic graphs by spanning tree automata ⋮ Tree Automata with Global Constraints ⋮ TREE AUTOMATA WITH GLOBAL CONSTRAINTS ⋮ Rigid tree automata and applications ⋮ Language theoretic properties of regular DAG languages ⋮ Rigid Tree Automata ⋮ Recognition of a Spanning Tree of Directed Acyclic Graphs by Tree Automata ⋮ Parameterized complexity of basic decision problems for tree automata

Cites Work

• Unnamed Item
• Unnamed Item
• Set constraints and automata
• Unification modulo ACUI plus distributivity axioms
• Automated Reasoning with Analytic Tableaux and Related Methods
• Mathematical Foundations of Computer Science 2003
• Unification of concept terms in description logics

This page was built for publication: Closure properties and decision problems of dag automata