Complexity of right-ideal, prefix-closed, and prefix-free regular languages

Brzozowski Janusz and Sinnamon Corwin: Complexity of right-ideal, prefix-closed, and prefix-free regular languages. In: Acta cybernetica, (23) 1. pp. 9-41. (2017)

[thumbnail of actacyb_23_1_2017_3.pdf]
Cikk, tanulmány, mű

Download (362kB) | Preview


A language L over an alphabet Σ is prefix-convex if, for any words x, y, z ϵ Σ* , whenever x and xyz are in L, then so is xy. Prefix-convex languages include right-ideal, prefix-closed, and prefix-free languages as special cases. We examine complexity properties of these special prefix-convex languages. In particular, we study the quotient/state complexity of boolean operations, product (concatenation), star, and reversal, the size of the syntactic semigroup, and the quotient complexity of atoms. For binary operations we use arguments with different alphabets when appropriate; this leads to higher tight upper bounds than those obtained with equal alphabets. We exhibit right-ideal, prefix-closed, and prefix-free languages that meet the complexity bounds for all the measures listed above.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2017
Volume: 23
Number: 1
ISSN: 0324-721X
Page Range: pp. 9-41
Language: English
Place of Publication: Szeged
Related URLs:
DOI: 10.14232/actacyb.23.1.2017.3
Uncontrolled Keywords: Kibernetika - nyelvészet, Matematikai nyelvészet
Additional Information: Bibliogr.: p. 39-41. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.01. Mathematics
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2018. Feb. 12. 08:27
Last Modified: 2022. Jun. 20. 14:17

Actions (login required)

View Item View Item