On the Expressive Power of Stateless Ordered Restart-Delete Automata

Simple item page
dc.date.accessioned2021-09-22T13:58:42Z
dc.date.available2021-09-22T13:58:42Z
dc.date.issued2021-03-13
dc.description.sponsorshipGefördert im Rahmen des Projekts DEALger
dc.identifierdoi:10.17170/kobra-202109084733
dc.identifier.urihttp://hdl.handle.net/123456789/13254
dc.language.isoengeng
dc.relation.doidoi:10.1007/s00224-020-10028-3
dc.rightsNamensnennung 4.0 International*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/*
dc.subjectrestarting automationeng
dc.subjectordered rewritingeng
dc.subjectcontext-free languageeng
dc.subjectdesciptional complexityeng
dc.subjectlimited context restarting automationeng
dc.subject.ddc600
dc.subject.swdAutomationger
dc.subject.swdRestart-Automatger
dc.subject.swdKontextfreie Spracheger
dc.titleOn the Expressive Power of Stateless Ordered Restart-Delete Automataeng
dc.typeAufsatz
dc.type.versionpublishedVersion
dcterms.abstractStateless ordered restart-delete automata (stl-ORD-automata) are studied. These are obtained from the stateless ordered restarting automata (stl-ORWW-automata) by introducing an additional restart-delete operation, which, based on the surrounding context, deletes a single letter. While the stl-ORWW-automata accept the regular languages, we show that the swift stl-ORD-automata yield a characterization for the class of context-free languages. Here a stl-ORD-automaton is called swift if it can move its window to any position after performing a restart. We also study the descriptional complexity of swift stl-ORD-automata and relate them to limited context restarting automata.eng
dcterms.accessRightsopen access
dcterms.creatorOtto, Friedrich
dcterms.source.identifiereissn:1433-0490
dcterms.source.issueIssue 7
dcterms.source.journalTheory of Computing Systemseng
dcterms.source.pageinfo1033-1068
dcterms.source.volumeVolume 65
kup.iskupfalse

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Otto2021_Article_OnTheExpressivePowerOfStateles.pdf
Size:
1.48 MB
Format:
Adobe Portable Document Format
Description:
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
3.03 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Artikel