Automata with two-sided pushdowns defined over free groups generated by reduced alphabets

Title:

Automata with two-sided pushdowns defined over free groups generated by reduced alphabets

Creator:

Blatný, Petr, Bidlo, Radek, and Meduna, Alexander

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:837e7a1b-0da4-4e42-92eb-4504078e968e
uuid:837e7a1b-0da4-4e42-92eb-4504078e968e

Subject:

pushdown automata, modifications, and recursively enumerable languages

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

This paper introduces and discusses a modification of pushdown automata. This modification is based on two-sided pushdowns into which symbols are pushed from both ends. These pushdowns are defined over free groups, not free monoids, and they can be shortened only by the standard group reduction. We demonstrate that these automata characterize the family of recursively enumerable languages even if the free groups are generated by no more than four symbols.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

[265]-278

Source:

Kybernetika | 2007 Volume:43 | Number:3

Harvested from:

CDK

Metadata only:

false