Loading...
Please wait, while we are loading the content...
Similar Documents
Bounded repairability of word languages
| Content Provider | Hyper Articles en Ligne (HAL) |
|---|---|
| Author | Benedikt, Michael Puppis, Gabriele Riveros, Cristian |
| Abstract | What do you do if a computational object (e.g. program trace) fails a specifica-tion? An obvious approach is to perform a repair : modify the object minimally to get something that satisfies the constraints. This approach has been in-vestigated in the database community, for integrity constraints, and in the AI community for propositional logics. Here we study how difficult it is to repair a document in the form of a string. Specifically, we consider number of edits that must be applied to an input string in order to satisfy a given target lan-guage. This number may be unbounded; our main contribution is to isolate the complexity of the bounded repair problem based on a characterization of the regular languages that admit bounded repairr. We consider the settings where the repair strategy is unconstrained and when the editing must be produced in a streaming way, i.e. by a letter-to-letter transducer. |
| Ending Page | 1321 |
| Page Count | 20 |
| Starting Page | 1302 |
| File Format | |
| ISSN | 00220000 |
| e-ISSN | 10902724 |
| DOI | 10.1016/j.jcss.2013.06.001 |
| Journal | Journal of Computer and System Sciences |
| Issue Number | 8 |
| Volume Number | 79 |
| Language | English |
| Publisher | Elsevier |
| Publisher Date | 2013-12-01 |
| Access Restriction | Open |
| Subject Keyword | bounded repair edit distance regular languages info Computer Science [cs] Formal Languages and Automata Theory [cs.FL] |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics |
