Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Pascal Caron Connect in order to contact the contributor
Submitted on : Tuesday, April 2, 2019 - 3:20:11 PM
Last modification on : Wednesday, March 2, 2022 - 10:10:09 AM

Links full text


  • HAL Id : hal-02088059, version 1
  • ARXIV : 1705.10625


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



Record views