The Library
WQO is decidable for factorial languages
Tools
Tools
Tools
Atminas, Aistis, Lozin, Vadim V. and Moshkov, M.. (2017) WQO is decidable for factorial languages. Information and Computation . ISSN 0890-5401 (In Press)
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
lan-wqo-jor-final.pdf - Accepted Version Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (308Kb) |
Official URL: https://www.journals.elsevier.com/information-and-...
Abstract
A language is factorial if it is closed under taking factors, i.e. contiguous subwords. Every factorial language can be described by an antidictionary, i.e. a minimal set of forbidden factors. We show that the problem of deciding whether a factorial language given by a finite antidictionary is well-quasi-ordered under the factor containment relation can be solved in polynomial time. We also discuss possible ways to extend our solution to permutations and graphs.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science > Mathematics | ||||
| Journal or Publication Title: | Information and Computation | ||||
| Publisher: | Academic Press | ||||
| ISSN: | 0890-5401 | ||||
| Official Date: | 20 July 2017 | ||||
| Dates: |
|
||||
| Status: | Peer Reviewed | ||||
| Publication Status: | In Press | ||||
| Related URLs: | |||||
| URI: | http://wrap.warwick.ac.uk/id/eprint/91011 |
Request changes or add full text files to a record
Actions (login required)
 |
View Item |
