A special case of a unary regular language containment
Litow, B. (2006) A special case of a unary regular language containment. Theory of Computing Systems, 39 (5). pp. 743-751.
![[img]](https://researchonline.jcu.edu.au/style/images/fileicons/application_pdf.png) |
PDF (Published Version)
- Published Version
Restricted to Repository staff only |
View at Publisher Website: http://dx.doi.org/10.1007/s00224-005-122...
2
2
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 n^{O(1)} bits, and whose periods are mutually coprime, deciding whether T is a subset of S is in n^{O(log n)} time. Dropping the mutual coprimality condition, this containment problem becomes NP-hard.
| Item ID: | 1602 |
|---|---|
| Item Type: | Article (Research - C1) |
| ISSN: | 1433-0490 |
| Keywords: | unary regular language; ultimately periodic set; NP-hard |
| Date Deposited: | 15 Aug 2007 |
| FoR Codes: | 08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080299 Computation Theory and Mathematics not elsewhere classified @ 50% 08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080201 Analysis of Algorithms and Complexity @ 50% |
| SEO Codes: | 97 EXPANDING KNOWLEDGE > 970101 Expanding Knowledge in the Mathematical Sciences @ 100% |
| Downloads: |
Total: 2 |
| More Statistics |
Actions (Repository Staff Only)
 |
Item Control Page |