Name
Abstract | ||
|---|---|---|
We use some 'natural' language operations, such as shuffle (scattered insertion) and scattered deletion to model noisy channels, that is, nondeterministic processes transforming words to words. In this spirit, we also introduce the operation of scattered substitution and derive the closure properties of the language families in the Chomsky hierarchy under this operation. Moreover, we consider a certain type of language inequations involving language operations and observe that, by varying the parameters of such an inequation, we can define families of codes such as prefix and infix, as well as families of error-detecting languages. Our results on this type of inequations include a characterization of the maximal solutions, which provides a uniform method for deciding whether a given regular code of the type defined by the inequation is maximal. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.jcss.2004.08.005 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
language operation,scattered insertion,language operations,error detection,error-detecting language,language equation,scattered deletion,language family,maximal solution,closure property,language inequations,chomsky hierarchy,maximal codes,certain type,scattered substitution,closure properties,natural language | Discrete mathematics,Context-sensitive language,Combinatorics,Nondeterministic algorithm,Inequation,Chomsky hierarchy,Communication channel,Prefix,Infix,Error detection and correction,Mathematics | Journal |
Volume | Issue | ISSN |
70 | 1 | Journal of Computer and System Sciences |
Citations | PageRank | References |
13 | 0.91 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lila Kari | 1 | 1123 | 124.45 |
| Stavros Konstantinidis | 2 | 283 | 31.10 |