1997•Unpublished venueRequires access

Characterizations of Recursively Enumerable Languages by Using Copy Languages

Gheorghe Pǎun, Arto K. Salomaa

Abstract

We give characterizations of recursively enumerable languages starting from copy languages, that is languages of the form fxx j x 2 Lg, where L is a regular language and x is the barred version of x. One characterization uses an intersection of morphic images of two copy languages, the other one uses a quotient of morphic images of two copy languages. As a consequence, we find similar characterizations of recursively enumerable languages starting from languages generated by (non-returning non-centralized) parallel communicating grammar systems with right-linear rules.

About this research paper

What this paper is about

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Key concepts: Recursively enumerable language, Abstract family of languages, Recursively enumerable set, Computer science, Characterization (materials science), Intersection (aeronautics), Regular language, Second-generation programming language