2017/05/30 by Caron, Pascal, Mignot, Ludovic, Miklarz, Clément
#68Q45 #F.1.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1705.10625
Brüggemann-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.