Name
Abstract | ||
|---|---|---|
A general framework of parallel insertion and deletion based on p-schemata is proposed. A p-schema is a set of tuples of words. When being used for parallel insertion of a language into a word, an element of p-schema specifies how to split the word into factors between which the language to be inserted. As its inverse operation, parallel deletion based on the p-schema is defined. Several algebraic properties of these operations such as closure properties of language classes under them are proved. The main contribution of this paper is to propose algorithms to solve language equations involving p-schema-based insertions or deletions based on syntactic congruence. These algorithms not only decide whether a given equation has a solution but construct the set of all of its maximal or minimal solutions. The algorithms are extensible so as to solve some multiple-variables equations and inequalities. Related undecidability results are also presented. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1142/S0129054111008945 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Contextual parallel insertion and deletion, p-schema, syntactic congruence, algorithms to solve multiple-variables language equations, language inequalities | Inverse,Discrete mathematics,Combinatorics,Tuple,Theoretical computer science,Algebraic properties,Congruence (geometry),Schema (psychology),Syntax,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 7 | 0129-0541 |
Citations | PageRank | References |
2 | 0.41 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lila Kari | 1 | 1123 | 124.45 |
| Shinnosuke Seki | 2 | 189 | 29.78 |