3
$\begingroup$

is there any tree automata model over unranked trees (that is with unbounded number of children for each node), such that:

  1. Checking non-emptiness and universality is decidable in elementary time,
  2. Construction of automata recognizing a projection and the complementation in polynomial size of the input automata, and
  3. Automata is non-deterministic and top-down.

The usual hedge-automata model does not suit me.

$\endgroup$
  • $\begingroup$ Any such model would have to be very weak, since even for finite tree automata (or coBuchi automata over infinite trees) complementation would not be in P (or rather, would be PSPACE hard), as a consequence of this result for word automata. Do you have any reasonable candidates that satisfy property 2? $\endgroup$ – Shaull Mar 4 '18 at 19:41
  • $\begingroup$ Thanks, for your remark. I was thinking about something completely different. I wanted to construct the automata recognizing projection and complementation in polynomial time. $\endgroup$ – Bartosz Bednarczyk Mar 4 '18 at 20:08
  • $\begingroup$ I know that for alternating parity tree automata you can do complementation easily, but to do projection, you need to translate it into non-deterministic one (which costs an exponential blowup). $\endgroup$ – Bartosz Bednarczyk Mar 4 '18 at 20:10
  • $\begingroup$ 1) constructing the automaton that recognizes the complement of a language is unlikely to be in P, if that model includes/subsumes word automata. 2) You're right that alternating parity automata can be easily complemented (due to the alternation), but you have huge cost in checking non-emptiness, since you essentially also need to check universality. Basically, if you have complementation and non-emptiness, then you can check universality, which is typically expensive. $\endgroup$ – Shaull Mar 4 '18 at 20:13
  • 2
    $\begingroup$ My friend and collaborator Andrey and I have been discussing exactly this. If you would like to join our discussion or collaborate, please let me know!! Hope that you have a nice day!! $\endgroup$ – Michael Wehar Mar 5 '18 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.