License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.51
URN: urn:nbn:de:0030-drops-127177
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12717/
Go to the corresponding LIPIcs Volume Portal

Jecker, Ismaël ; Kupferman, Orna ; Mazzocchi, Nicolas

Unary Prime Languages

pdf-format:
LIPIcs-MFCS-2020-51.pdf (0.6 MB)

Abstract

A regular language L of finite words is composite if there are regular languages L₁,L₂,…,L_t such that L = ⋂_{i = 1}^t L_i and the index (number of states in a minimal DFA) of every language L_i is strictly smaller than the index of L. Otherwise, L is prime. Primality of regular languages was introduced and studied in [O. Kupferman and J. Mosheiff, 2015], where the complexity of deciding the primality of the language of a given DFA was left open, with a doubly-exponential gap between the upper and lower bounds. We study primality for unary regular languages, namely regular languages with a singleton alphabet. A unary language corresponds to a subset of ℕ, making the study of unary prime languages closer to that of primality in number theory. We show that the setting of languages is richer. In particular, while every composite number is the product of two smaller numbers, the number t of languages necessary to decompose a composite unary language induces a strict hierarchy. In addition, a primality witness for a unary language L, namely a word that is not in L but is in all products of languages that contain L and have an index smaller than L’s, may be of exponential length. Still, we are able to characterize compositionality by structural properties of a DFA for L, leading to a LogSpace algorithm for primality checking of unary DFAs.

BibTeX - Entry

@InProceedings{jecker_et_al:LIPIcs:2020:12717,
  author =	{Isma{\"e}l Jecker and Orna Kupferman and Nicolas Mazzocchi},
  title =	{{Unary Prime Languages}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{51:1--51:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12717},
  URN =		{urn:nbn:de:0030-drops-127177},
  doi =		{10.4230/LIPIcs.MFCS.2020.51},
  annote =	{Keywords: Deterministic Finite Automata (DFA), Regular Languages, Primality}
}

Keywords: Deterministic Finite Automata (DFA), Regular Languages, Primality
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI