On the decidability of $k$-Block determinism - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

## On the decidability of $k$-Block determinism

Ludovic Mignot
• Function : Author

#### 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.

#### Domains

Computer Science [cs]

### Dates and versions

hal-02088059 , version 1 (02-04-2019)

### Identifiers

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

### Cite

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

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

149 View