On the state complexity of the reverse of R- and J-trivial regular languages

DOI10.1007/978-3-642-39310-5_14MaRDI QIDQ2843091zbMATH OpenOpenAlexFDO

Authors Galina Jirásková, Tomáš Masopust

Publication date 9 August 2013

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

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

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

Abstract: The tight upper bound on the state complexity of the reverse of R-trivial and J-trivial regular languages of the state complexity n is 2^{n-1}. The witness is ternary for R-trivial regular languages and (n-1)-ary for J-trivial regular languages. In this paper, we prove that the bound can be met neither by a binary R-trivial regular language nor by a J-trivial regular language over an (n-2)-element alphabet. We provide a characterization of tight bounds for R-trivial regular languages depending on the state complexity of the language and the size of its alphabet. We show the tight bound for J-trivial regular languages over an (n-2)-element alphabet and a few tight bounds for binary J-trivial regular languages. The case of J-trivial regular languages over an (n-k)-element alphabet, for 2 <= k <= n-3, is open.

Recommendations

Cited in

(3)

This page was built for publication: On the state complexity of the reverse of \({\mathcal R}\)- and \({\mathcal J}\)-trivial regular languages

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