A string x is an outfix of a string y if there is a string w such that x₁wx₂ = y, where x = x₁x₂ 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