A Special Case of a Unary Regular Language Containment |
| |
Authors: | B Litow |
| |
Affiliation: | (1) School of Information Technology, James Cook University, Townsville, Queensland 4811, Australia |
| |
Abstract: | Given an n-state unary finite automaton accepting a language T, and an ultimately
periodic set S given as a union of arithmetic progressions that can be represented using
nO(1) bits, and whose periods are mutually coprime,
deciding whether T ⫅ S is in nO(log n) time. Dropping the mutual coprimality
condition, this containment problem becomes NP-hard. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|