CÁC BÀI BÁO KHOA HỌC 00:52:45 Ngày 24/10/2019 GMT+7
Outfix-free regular languages and prime outfix-free decomposition

A string x is an outfix of a string y if there is a string w such that x1wx2 = y, where x = x1x2 and a set X of strings is outfix-free if no string in X is an outfix of any other string in X. We examine the outfix-free regular languages. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines the outfix-freeness of regular languages. We consider two cases: A language is given as a set of strings and a language is given by an acyclic deterministic finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfix-free regular languages and design a linear-time prime outfix-free decomposition algorithm for outfix-free regular languages. We demonstrate the uniqueness of prime outfix-free decomposition. © Springer-Verlag Berlin Heidelberg 2005.

 Han Y.-S., Wood D. 710.pdf    Gửi cho bạn bè Từ khóa : Algorithms; Automation; Decomposition; Logic design; Polynomials; Finite-state automaton; Outfix-free decomposition; Outfix-free regular languages; Formal languages