Skip to Main content Skip to Navigation
Journal articles

On the hierarchy of generalizations of one-unambiguous regular languages

Pascal Caron 1, 2 Ludovic Mignot 1, 2 Clément Miklarz 1, 2
1 CA - LITIS - Equipe Combinatoire et algorithmes
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : A regular language is lookahead (resp. block) deterministic if it is specified by a lookahead (resp. block) deterministic regular expression. These two subclasses of regular languages have been respectively introduced by Han and Wood for lookahead determinism and by Giammarresi et al. for block determinism, as a possible extension of one-unambiguous languages defined and characterized by Brüggemann-Klein and Wood. In this paper, we study the hierarchies and inclusion links of these families. We first show that each block deterministic language is the alphabetical image of some one-unambiguous language. Moreover, we show that deciding the block determinism of a regular language from its minimal DFA does not only require state elimination. Han and Wood state that there is a proper hierarchy in block deterministic languages, but prove it using this erroneous requirement. However, we prove their statement by giving our own parametrized family. We also prove that there is a proper hierarchy in lookahead deterministic languages by studying particular properties of unary regular expressions. Finally, using our valid results, we confirm that the family of block deterministic languages is strictly included in the one of lookahead deterministic languages by showing that any block deterministic unary language is one-unambiguous.
Document type :
Journal articles
Complete list of metadatas

https://hal-normandie-univ.archives-ouvertes.fr/hal-02088016
Contributor : Pascal Caron <>
Submitted on : Tuesday, April 2, 2019 - 3:05:03 PM
Last modification on : Tuesday, July 23, 2019 - 9:18:49 AM

Identifiers

Citation

Pascal Caron, Ludovic Mignot, Clément Miklarz. On the hierarchy of generalizations of one-unambiguous regular languages. Theoretical Computer Science, Elsevier, 2017, 679, pp.95-106. ⟨10.1016/j.tcs.2016.07.004⟩. ⟨hal-02088016⟩

Share

Metrics

Record views

53