DROPS

Document

Deterministic Automata on Unranked Trees

Authors: Wolfgang Thomas, Julien Christau, and Christof Löding

Published in: Dagstuhl Seminar Proceedings, Volume 5061, Foundations of Semistructured Data (2005)

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.

Cite as

Wolfgang Thomas, Julien Christau, and Christof Löding. Deterministic Automata on Unranked Trees. In Foundations of Semistructured Data. Dagstuhl Seminar Proceedings, Volume 5061, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.05061.3},
  URN =		{urn:nbn:de:0030-drops-2281},
  doi =		{10.4230/DagSemProc.05061.3},
  annote =	{Keywords: Automata, unranked trees, parikh automata}
}

Search Results

Documents authored by Christau, Julien

Deterministic Automata on Unranked Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message