On the decidability of $k$-Block determinism

Pascal Caron (1, 2) , Clément Miklarz (1, 2) , Ludovic Mignot (2)

1 CA - LITIS - Equipe Combinatoire et algorithmes
2 UNIROUEN - Université de Rouen Normandie

Br\"uggemann-Klein and Wood define a one-unambiguous regular language as a language that can be recognized by a deterministic Glushkov automaton. They give a procedure performed on the minimal DFA, the BW-test, to decide whether a language is one-unambiguous. Block determinism is an extension of one-unambiguity while considering non-empty words as symbols and prefix-freeness as determinism. A block automaton is compact if it does not have two equivalent states (same right language). We showed that a language is $k$-block deterministic if it is recognized by some deterministic $k$-block automaton passing the BW-test. In this paper, we show that any $k$-block deterministic language is recognized by a compact deterministic $k$-block automaton passing the BW-test. We also give a procedure which enumerates, for a given language, the finite set of compact deterministic $k$-block automata. It gives us a decidable procedure to test whether a language is $k$-block deterministic.

Domaines: Informatique [cs]

Pascal Caron, Clément Miklarz, Ludovic Mignot. On the decidability of $k$-Block determinism. 2019. ⟨hal-02088059⟩