License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05061.3
URN: urn:nbn:de:0030-drops-2281
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/228/
Go to the corresponding Portal

Thomas, Wolfgang ; Christau, Julien ; Löding, Christof

Deterministic Automata on Unranked Trees

pdf-format:
05061.ThomasWolfgang.Paper.228.pdf (0.2 MB)

Abstract

We investigate bottom-up and top-down deterministic automata
on unranked trees. We show that for an appropriate definition of
bottom-up deterministic automata it is possible to minimize the number
of states efficiently and to obtain a unique canonical representative of
the accepted tree language. For top-down deterministic automata it is
well known that they are less expressive than the non-deterministic ones.
By generalizing a corresponding proof from the theory of ranked tree automata
we show that it is decidable whether a given regular language
of unranked trees can be recognized by a top-down deterministic automaton.
The standard deterministic top-down model is slightly weaker
than the model we use, where at each node the automaton can scan the
sequence of the labels of its successors before deciding its next move.

BibTeX - Entry

@InProceedings{thomas_et_al:DagSemProc.05061.3,
  author =	{Thomas, Wolfgang and Christau, Julien and L\"{o}ding, Christof},
  title =	{{Deterministic Automata on Unranked Trees}},
  booktitle =	{Foundations of Semistructured Data},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5061},
  editor =	{Frank Neven and Thomas Schwentick and Dan Suciu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/228},
  URN =		{urn:nbn:de:0030-drops-2281},
  doi =		{10.4230/DagSemProc.05061.3},
  annote =	{Keywords: Automata, unranked trees, parikh automata}
}

Keywords: Automata, unranked trees, parikh automata
Collection: 05061 - Foundations of Semistructured Data
Issue Date: 2005
Date of publication: 10.08.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI