| |
Quotient Complexity of Closed Languages
- 作者:Janusz Brzozowski (1)
Galina Jirásková (2) Chenglong Zou (3)
- 关键词:Closed language ; Finite automaton ; Quotient complexity ; Regular language ; State complexity
- 刊名:Theory of Computing Systems
- 出版年:2014
- 出版时间:February 2014
- 年:2014
- 卷:54
- 期:2
- 页码:277-292
- 全文大小:595 KB
- 作者单位:Janusz Brzozowski (1)
Galina Jirásková (2) Chenglong Zou (3)
1. David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada, N2L 3G1 2. Mathematical Institute, Slovak Academy of Sciences, Gre?ákova 6, 040 01, Ko?ice, Slovakia 3. Department of Mathematics, University of British Columbia, Vancouver, BC, Canada, V6T 1Z4
- ISSN:1433-0490
文摘
A language L is prefix-closed if, whenever a word w is in?L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in an analogous way, where by factor we mean contiguous subsequence, and by subword we mean scattered subsequence. We study the state complexity (which we prefer to call quotient complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star, and reversal in each of the four classes of closed languages. We show that repeated applications of positive closure and complement to a closed language result in at most four distinct languages, while Kleene closure and complement give at most eight.
| |
NGLC 2004-2010.National Geological Library of China All Rights Reserved.
Add:29 Xueyuan Rd,Haidian District,Beijing,PRC. Mail Add: 8324 mailbox 100083
For exchange or info please contact us via email.
| |