On the hierarchy of block deterministic languages

DOI10.1007/978-3-319-22360-5_6zbMATH Open1465.68137arXiv1512.05475OpenAlexW1180644322MaRDI QIDQ2947409FDOQ2947409

Authors: Pascal Caron, Ludovic Mignot, Clément Miklarz 

Publication date: 23 September 2015

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Abstract: A regular language is $k$-lookahead deterministic (resp. $k$-block deterministic) if it is specified by a $k$-lookahead deterministic (resp. $k$-block deterministic) regular expression. These two subclasses of regular languages have been respectively introduced by Han and Wood ($k$-lookahead determinism) and by Giammarresi et al. ($k$-block determinism) as a possible extension of one-unambiguous languages defined and characterized by Br"uggemann-Klein and Wood. In this paper, we study the hierarchy and the inclusion links of these families. We first show that each $k$-block deterministic language is the alphabetic image of some one-unambiguous language. Moreover, we show that the conversion from a minimal DFA of a $k$-block deterministic regular language to a $k$-block deterministic automaton not only requires state elimination, and that the proof given by Han and Wood of a proper hierarchy in $k$-block deterministic languages based on this result is erroneous. Despite these results, we show by giving a parameterized family that there is a proper hierarchy in $k$-block deterministic regular languages. We also prove that there is a proper hierarchy in $k$-lookahead deterministic regular languages by studying particular properties of unary regular expressions. Finally, using our valid results, we confirm that the family of $k$-block deterministic regular languages is strictly included into the one of $k$-lookahead deterministic regular languages by showing that any $k$-block deterministic unary language is one-unambiguous.

Full work available at URL: https://arxiv.org/abs/1512.05475

Recommendations

• On the hierarchy of generalizations of one-unambiguous regular languages
• scientific article; zbMATH DE number 2044501
• Generalizations of 1-deterministic regular languages
• Deciding determinism of regular languages
• \((k,l)\)-unambiguity and quasi-deterministic structures: an alternative for the determinization

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• THE ABSTRACT THEORY OF AUTOMATA
• Title not available (Why is that?)
• Characterization of Glushkov automata
• Title not available (Why is that?)
• One-unambiguous regular languages
• Title not available (Why is that?)
• Generalizations of 1-deterministic regular languages
• (k,l)-Unambiguity and Quasi-Deterministic Structures: An Alternative for the Determinization

Cited In (2)

• Title not available (Why is that?)
• Generalizations of 1-deterministic regular languages

This page was built for publication: On the hierarchy of block deterministic languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947409)