Homomorphic Representations of Certain Classes of Languages

Franz J. Brandenburg
Additional contact information
Franz J. Brandenburg: Universität Passau, Lehrstuhl für Informatik

A chapter in Advances in Algorithms, Languages, and Complexity, 1997, pp 93-110 from Springer

Abstract: Abstract The use of homomorphisms for simple representations of certain classes of languages is investigated. The homomorphisms are combined to tuples which then define a homomorphic replication. This operation plays an important role in the characterization of classes of languages like BNP and MULTI-RESET. If the homomophisms of a tuple coincide on a string, then their homomorphic equality is defined. This operation is closely related to equality sets of homomorphisms and is extremely powerful. We provide purely homomorphic characterizations of the regular sets and the recursively enumerable sets, and of the classes MULTI-RESET and BNP. Starting from {$}, three homomorphisms suffice to represent every regular set and four homomorphisms suffice to represent every recursively enumerable set. For these statements we make extensive use of notions, techniques and results introduced by Professor Ron Book.

Keywords: nondeterministic multitape Turing machines; reversal-bounded tapes and reset tapes; homomorphic replication; homomorphic equality (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3394-4_4

Ordering information: This item can be ordered from
http://www.springer.com/9781461333944

DOI: 10.1007/978-1-4613-3394-4_4

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().