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 metadatas

https://hal-normandie-univ.archives-ouvertes.fr/hal-02088059
Contributor : Pascal Caron <>
Submitted on : Tuesday, April 2, 2019 - 3:20:11 PM
Last modification on : Wednesday, April 3, 2019 - 1:59:59 AM

Links full text

Identifiers

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

Citation

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

Share

Metrics

Record views

98