On the hierarchy of block deterministic languages

DOI10.1007/978-3-319-22360-5_6MaRDI QIDQ2947409zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

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

Cites work

• scientific article; zbMATH DE number 2044501 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• Characterization of Glushkov automata
• Generalizations of 1-deterministic regular languages
• One-unambiguous regular languages
• THE ABSTRACT THEORY OF AUTOMATA
• \((k,l)\)-unambiguity and quasi-deterministic structures: an alternative for the determinization

Cited in

(3)

• On the hierarchy of generalizations of one-unambiguous regular languages
• scientific article; zbMATH DE number 2044501 (Why is no real title available?)
• 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)