Quotient complexity of bifix-, factor-, and subword-free regular languages

Brzozowski Janusz and Jirásková Galina and Li Baiyu and Smith Joshua: Quotient complexity of bifix-, factor-, and subword-free regular languages. In: Acta cybernetica, (21) 4. pp. 507-527. (2014)

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

Download (237kB) | Preview


A language L is prefix-free if whenever words u and v are in L and u is a prefix of v, then u = v. Suffix-, factor-, and subword-free languages are defined similarly, where by "subword" we mean "subsequence", and a language is bifix-free if it is both prefix- and suffix-free. These languages have important applications in coding theory. The quotient complexity of an operation on regular languages is defined as the number of left quotients of the result of the operation as a function of the numbers of left quotients of the operands. The quotient complexity of a regular language is the same as its state complexity, which is the number of states in the complete minimal deterministic finite automaton accepting the language. The state/quotient complexity of operations in the classes of prefix- and suffix-free languages has been studied before. Here, we study the complexity of operations in the classes of bifix-, factor-, and subword-free languages. We find tight upper bounds on the quotient complexity of intersection, union, difference, symmetric difference, concatenation, star, and reversal in these three classes of languages.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2014
Volume: 21
Number: 4
ISSN: 0324-721X
Page Range: pp. 507-527
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38538/
DOI: 10.14232/actacyb.21.4.2014.1
Uncontrolled Keywords: Számítástechnika
Additional Information: Bibliogr.: p. 525-527. és a lábjegyzetekben ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 17. 10:37
Last Modified: 2022. Jun. 20. 08:22
URI: http://acta.bibl.u-szeged.hu/id/eprint/34823

Actions (login required)

View Item View Item