?-Clearing Restarting Automata and CFL

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10104127" target="_blank" >RIV/00216208:11320/11:10104127 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-642-22321-1_14" target="_blank" >http://dx.doi.org/10.1007/978-3-642-22321-1_14</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-22321-1_14" target="_blank" >10.1007/978-3-642-22321-1_14</a>

Result language

angličtina

Original language name

?-Clearing Restarting Automata and CFL

Original language description

?-clearing restarting automata represent a new restricted model of restarting automata which, based on a limited context, can either delete a substring of the current content of its tape or replace a substring by a special auxiliary symbol ?, which cannot be overwritten anymore, but it can be deleted later. The main result of this paper consists in proving that besides their limited operations, ?-clearing restarting automata recognize all context-free languages.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2011

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Lecture Notes in Computer Science

ISBN

978-3-642-22320-4

ISSN

0302-9743

e-ISSN

—

Number of pages

12

Pages from-to

153-164

Publisher name

Springer-Verlag

Place of publication

Berlin

Event location

Milano, Itálie

Event date

Jul 19, 2011

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—