On prefixal one-rule string rewrite systems
| Autor: | Yves Roos, Michel Latteux |
|---|---|
| Přispěvatelé: | Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2019 |
| Předmět: |
General Computer Science
Computer science One-rule string rewrite system Context-free language 0102 computer and information sciences 02 engineering and technology Context free language 16. Peace & justice 01 natural sciences [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] Theoretical Computer Science Decidability Prefix Algebra TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics Computer Science::Logic in Computer Science 0202 electrical engineering electronic engineering information engineering Computer Science::Programming Languages 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2019, 795, pp.240-256. ⟨10.1016/j.tcs.2019.07.004⟩ Theoretical Computer Science, 2019, 795, pp.240-256. ⟨10.1016/j.tcs.2019.07.004⟩ |
| ISSN: | 0304-3975 1879-2294 |
| DOI: | 10.1016/j.tcs.2019.07.004 |
| Popis: | International audience; Prefixal one-rule string rewrite systems are one-rule string rewrite systems for which the left-hand side of the rule is a prefix of the right-hand side of the rule. String rewrite systems induce a transformation over languages: from a starting word, one can associate all its descendants. We prove, in this work, that the transformation induced by a prefixal one-rule rewrite system always transforms a finite language into a context-free language, a property that is surprisingly not satisfied by arbitrary one-rule rewrite systems. We also give here a decidable characterization of the prefixal one-rule rewrite systems whose induced transformation is a rational transduction. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect