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] 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 (Refereed Research - C1)
Keywords: unary regular language; ultimately periodic set; NP-hard
ISSN: 1433-0490
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 Item Control Page