<p>I would need to know if somebody in the literature studied the concept of <em>unambiguity</em> in the context of <em>alternating finite automata</em> (AFA).</p>
<p>Of course there's a lot of work on unambiguity in NFAs, and I also found much work on unambiguity in alternating Turing machines (e.g. starting from <a href="https://link.springer.com/article/10.1007/s00224-007-2014-y" rel="nofollow noreferrer">here</a>).</p>
<p>However, the definition of <em>unambiguous alternating Turing machine</em> (UATM) does not map very well to AFAs because in UATMs we have existential and universal states whereas AFAs are defined in terms of the evolution of Boolean functions.</p>
<p>I can imagine how one may circumvent this definition mismatch but I would rather not reinvent the wheel both for the definition and for basic results resulting from it.</p>
<p>I suppose a suitable definition should have the following features:</p>
<ol>
<li>unambiguous NFAs with only disjunctive formulas should be unambiguous NFas</li>
<li>suitably restricted unambiguous ATMs should be unambiguous AFAs</li>
</ol>
<p>So has anybody out there defined and studied unambiguous AFAs?</p>

CC BY-SA 4.0
2024-08-13T17:46:52.143Z
You could define unambiguity as "there's at most one accepting run-tree". But what's the motivation for this model?
Shaull
CC BY-SA 4.0
2024-08-13T17:51:16.543Z
Thanks! I still have not much practice with AFAs but I have some problems talking about the run-tree, because in all the technical presentations I find (including the original by Chandra Kozen and Stockmeyer) there are no trees in the semantics. Some presentations talk about AFAs in a way that make the run tree emerge naturally but I only found informal presentations of this kind, and no formal equivalence of the two presentations.
Nicola Gigante
CC BY-SA 4.0
2024-08-13T18:23:20.473Z
Btw, "there is at most one accepting run-tree" does not match the definition used for UATMs, where it is also required that universal nodes can be refuted only in one way.
Nicola Gigante
CC BY-SA 4.0
2024-08-13T18:39:23.800Z
I guess the main question is: what do you want to model? Once you pick some desirable behaviours of the model, then it would be easier to come up with relevant definitions, and see if related models have been studied.
Shaull
CC BY-SA 4.0
2024-08-14T05:40:35.217Z
Hi, I don't understand "AFAs are defined in terms of the evolution of Boolean functions". First, do you mean "evaluation"? Second, can't you also define AFAs with existential and universal states?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-08-14T05:44:05.727Z
About references, this paper https://arxiv.org/abs/1907.02887 seems to introduce a notion of unambiguity for alternating automata, although I'm not sure about the formalism (and I'm not sure whether what they are doing makes sense outside of the context of infinite words).
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-08-14T05:49:46.083Z
That’s a nice pointer, thanks!
Nicola Gigante
<reference-request><automata-theory><alternation>
Definition of unambiguity in alternating finite automata
Nicola Gigante
# Definition of unambiguity in alternating finite automata

(Asked by: username_0 on 2024-08-13)

I would need to know if somebody in the literature studied the concept of *unambiguity* in the context of *alternating finite automata* (AFA).

Of course there's a lot of work on unambiguity in NFAs, and I also found much work on unambiguity in alternating Turing machines (e.g. starting from [here](https://link.springer.com/article/10.1007/s00224-007-2014-y)).

However, the definition of *unambiguous alternating Turing machine* (UATM) does not map very well to AFAs because in UATMs we have existential and universal states whereas AFAs are defined in terms of the evolution of Boolean functions.

I can imagine how one may circumvent this definition mismatch but I would rather not reinvent the wheel both for the definition and for basic results resulting from it.

I suppose a suitable definition should have the following features:

1. unambiguous NFAs with only disjunctive formulas should be unambiguous NFas
2. suitably restricted unambiguous ATMs should be unambiguous AFAs

So has anybody out there defined and studied unambiguous AFAs?

**Tags:** reference-request, automata-theory, alternation
> **Comments:**
> **username_1**: You could define unambiguity as "there's at most one accepting run-tree". But what's the motivation for this model?  
> **username_0**: Thanks! I still have not much practice with AFAs but I have some problems talking about the run-tree, because in all the technical presentations I find (including the original by Chandra Kozen and Stockmeyer) there are no trees in the semantics. Some presentations talk about AFAs in a way that make the run tree emerge naturally but I only found informal presentations of this kind, and no formal equivalence of the two presentations.  
> **username_0**: Btw, "there is at most one accepting run-tree" does not match the definition used for UATMs, where it is also required that universal nodes can be refuted only in one way.  
> **username_1**: I guess the main question is: what do you want to model? Once you pick some desirable behaviours of the model, then it would be easier to come up with relevant definitions, and see if related models have been studied.  
> **username_2**: Hi, I don't understand "AFAs are defined in terms of the evolution of Boolean functions". First, do you mean "evaluation"? Second, can't you also define AFAs with existential and universal states?  
> **username_2**: About references, this paper https://arxiv.org/abs/1907.02887 seems to introduce a notion of unambiguity for alternating automata, although I'm not sure about the formalism (and I'm not sure whether what they are doing makes sense outside of the context of infinite words).  
> **username_0**: That’s a nice pointer, thanks!  

---

## 0 answers

