<p>I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter <span class="math-container">$a$</span> of the alphabet, the automaton has at most one transition labeled with <span class="math-container">$a$</span>. (Of course, the automaton is then necessarily a partial deterministic automaton.) <strong>Is there a name for this class of regular languages?</strong></p>
<p>These languages are quite limited but not entirely trivial either, for instance you could have <span class="math-container">$(ab)^*$</span>, <span class="math-container">$ab^*|cd^*$</span>, or <span class="math-container">$(ab)^*a$</span> (which I guess cannot be written as a regular expression with only one occurrence of each letter, so my class is more general than imposing the analogous requirement on regular expressions). These automata are clearly <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton#Local_automata" rel="noreferrer">local automata</a>, so this is a subclass of the local languages. These automata are also <a href="https://en.wikipedia.org/wiki/Aperiodic_finite_state_automaton" rel="noreferrer">aperiodic</a>, so these languages are star-free. Of course, for any alphabet, there are only finitely many languages of this kind over the alphabet.</p>
<p>I thought this class was pretty natural, but looking around, I could not find anything about it. Does it have a name, or has it been studied somehow?</p>

CC BY-SA 4.0
2020-11-01T22:49:52.473Z
It seems that your class can be defined as the smallest class $C$ such that every regular language is the projection via a length-preserving morphism of a language from $C$. Maybe this algebraic point of view can help...
Denis
CC BY-SA 4.0
2020-11-02T09:10:19.167Z
Actually, a deterministic automaton has exactly as many $a$-transitions as it has states. Do you mean something like a “partial deterministic” automaton?
Emil Jeřábek
CC BY-SA 4.0
2020-11-02T09:34:12.313Z
@EmilJeřábek From the examples I think it means that every other transition goes to a rejection state.
Wei Zhan
CC BY-SA 4.0
2020-11-02T10:45:37.497Z
Yes, I meant partial deterministic. Sorry, I'm used to automata being partial by default, and yes it means that arrows that are not defined implicitly lead to a rejection state. Edited the question accordingly, thanks.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-11-02T10:46:03.367Z
@Denis: I agree with your comment, though I'm not sure how to use it. :)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-11-02T11:46:25.227Z
Also a side remark: if there is an automaton satisfying your constraint, it is necessarily the minimal automaton. So it's easy to decide membership in the class by just computing the minimal automaton.
Denis
CC BY-SA 4.0
2020-11-02T12:27:39.567Z
They are a subclass of the *reversible* automata but I don't know if they are "studied" or have an "official" name; see for example [On Reversible Automata](https://www.irif.fr/~jep/PDF/Reversible.pdf). Given a DFA you can expand its alphabet to assign an unique letter to each transition, the resulting language is the language of all possible traversals ("traces") of the original DFA.
Marzio De Biasi
CC BY-SA 4.0
2020-11-02T13:10:13.837Z
@Denis: I'm not too sure I understand why the minimal automaton would work (it's usually taken to be minimal in terms of number of states, not transitions), though clearly it's decidable to test membership as there's a bound on the automaton size and equivalence of regular languages is decidable.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-11-02T13:10:16.937Z
@MarzioDeBiasi: I didn't know this notion of reversible automata and reversible languages, but I agree my languages are indeed a subclass of reversible languages, thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-11-02T16:03:53.973Z
@a3nm if an automaton works, then there is no way to further minimize it by merging states, since the outgoing transitions of two different states have completely different labels.
Denis
CC BY-SA 4.0
2020-11-02T16:05:26.153Z
@Denis: ah, thanks, that makes sense.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-11-02T22:52:32.020Z
Also note that once you fix the alphabet the number of distinct languages you can get with your model is finite ($|Q| \leq |\Sigma|$ must hold); if you consider the languages obtained by incresing $\Sigma$ size, then you get the class of distinct DFA "traces" (as said above).
Marzio De Biasi
CC BY-SA 4.0
2020-11-03T08:47:13.987Z
@MarzioDeBiasi: Yes, that was already in my initial question. This is simply because the number of transitions, hence of relevant states, is bounded by the alphabet size.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-09-25T11:10:27.763Z
Do you allow to have multiple initial states (as in NFAs) or only one (as in DFAs)? This does not give the same class of languages it seems: if you allow multiple initial states then $L= (ab)^*a | c$ is in your class, but it is not if you impose only one initial state
M.Monet
CC BY-SA 4.0
2024-09-25T12:44:50.223Z
@M.Monet: to clarify what we know (also from discussions together ;)), there are 3 possible models of automata with at most one transition per letter: (1.) DFAs, (2.) DFAs except that there are multiple initial states; (3.) NFAs also allowing ε-transitions. I agree the question is ambiguous about whether (1.) or (2.) is intended, I think both make sense.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-09-25T12:44:55.457Z
In terms of which languages are recognized, we now know that (3.) recognize exactly the local languages. Clearly (1.) is included in (2.) which is included in (3.). Your example would suggest that the inclusion of (1.) in (2.) is strict. I think we expect the inclusion of (2.) in (3.) to be also strict. We don't currently have characterizations of which languages are recognized by (1.), or by (2.).
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-10-01T18:50:26.607Z
Also posting here a remark by @BrunoGU who unfortunately doesn't have yet permission to comment: the languages in the question are closed under intersection (by the product automaton construction), but not under union
Antoine Amarilli 'a3nm'
<reference-request><fl.formal-languages><automata-theory><regular-language>
Regular languages accepted by an automaton with at most one transition per letter
Antoine Amarilli 'a3nm'
# Regular languages accepted by an automaton with at most one transition per letter

(Asked by: username_0 on 2020-11-01)

I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one transition labeled with $a$. (Of course, the automaton is then necessarily a partial deterministic automaton.) **Is there a name for this class of regular languages?**

These languages are quite limited but not entirely trivial either, for instance you could have $(ab)^\*$, $ab^\*|cd^\*$, or $(ab)^\*a$ (which I guess cannot be written as a regular expression with only one occurrence of each letter, so my class is more general than imposing the analogous requirement on regular expressions). These automata are clearly [local automata](https://en.wikipedia.org/wiki/Deterministic_finite_automaton#Local_automata), so this is a subclass of the local languages. These automata are also [aperiodic](https://en.wikipedia.org/wiki/Aperiodic_finite_state_automaton), so these languages are star-free. Of course, for any alphabet, there are only finitely many languages of this kind over the alphabet.

I thought this class was pretty natural, but looking around, I could not find anything about it. Does it have a name, or has it been studied somehow?

**Tags:** reference-request, fl.formal-languages, automata-theory, regular-language

> **Comments:**
> **username_1**: It seems that your class can be defined as the smallest class $C$ such that every regular language is the projection via a length-preserving morphism of a language from $C$. Maybe this algebraic point of view can help...  
> **username_2**: Actually, a deterministic automaton has exactly as many $a$-transitions as it has states. Do you mean something like a “partial deterministic” automaton?  
> **username_3**: @EmilJeřábek From the examples I think it means that every other transition goes to a rejection state.  
> **username_0**: Yes, I meant partial deterministic. Sorry, I'm used to automata being partial by default, and yes it means that arrows that are not defined implicitly lead to a rejection state. Edited the question accordingly, thanks.  
> **username_0**: @username_1: I agree with your comment, though I'm not sure how to use it. :)  
> **username_1**: Also a side remark: if there is an automaton satisfying your constraint, it is necessarily the minimal automaton. So it's easy to decide membership in the class by just computing the minimal automaton.  
> **username_4**: They are a subclass of the *reversible* automata but I don't know if they are "studied" or have an "official" name; see for example [On Reversible Automata](https://www.irif.fr/~jep/PDF/Reversible.pdf). Given a DFA you can expand its alphabet to assign an unique letter to each transition, the resulting language is the language of all possible traversals ("traces") of the original DFA.  
> **username_0**: @username_1: I'm not too sure I understand why the minimal automaton would work (it's usually taken to be minimal in terms of number of states, not transitions), though clearly it's decidable to test membership as there's a bound on the automaton size and equivalence of regular languages is decidable.  
> **username_0**: @MarzioDeBiasi: I didn't know this notion of reversible automata and reversible languages, but I agree my languages are indeed a subclass of reversible languages, thanks!  
> **username_1**: @a3nm if an automaton works, then there is no way to further minimize it by merging states, since the outgoing transitions of two different states have completely different labels.  
> **username_0**: @username_1: ah, thanks, that makes sense.  
> **username_4**: Also note that once you fix the alphabet the number of distinct languages you can get with your model is finite ($|Q| \leq |\Sigma|$ must hold); if you consider the languages obtained by incresing $\Sigma$ size, then you get the class of distinct DFA "traces" (as said above).  
> **username_0**: @MarzioDeBiasi: Yes, that was already in my initial question. This is simply because the number of transitions, hence of relevant states, is bounded by the alphabet size.  
> **username_5**: Do you allow to have multiple initial states (as in NFAs) or only one (as in DFAs)? This does not give the same class of languages it seems: if you allow multiple initial states then $L= (ab)^*a | c$ is in your class, but it is not if you impose only one initial state  
> **username_0**: @username_5: to clarify what we know (also from discussions together ;)), there are 3 possible models of automata with at most one transition per letter: (1.) DFAs, (2.) DFAs except that there are multiple initial states; (3.) NFAs also allowing ε-transitions. I agree the question is ambiguous about whether (1.) or (2.) is intended, I think both make sense.  
> **username_0**: In terms of which languages are recognized, we now know that (3.) recognize exactly the local languages. Clearly (1.) is included in (2.) which is included in (3.). Your example would suggest that the inclusion of (1.) in (2.) is strict. I think we expect the inclusion of (2.) in (3.) to be also strict. We don't currently have characterizations of which languages are recognized by (1.), or by (2.).  
> **username_0**: Also posting here a remark by @BrunoGU who unfortunately doesn't have yet permission to comment: the languages in the question are closed under intersection (by the product automaton construction), but not under union  

---

## 0 answers

