Show simple item record

On the Expressive Power of Stateless Ordered Restart-Delete Automata

dc.date.accessioned2021-09-22T13:58:42Z
dc.date.available2021-09-22T13:58:42Z
dc.date.issued2021-03-13
dc.identifierdoi:10.17170/kobra-202109084733
dc.identifier.urihttp://hdl.handle.net/123456789/13254
dc.description.sponsorshipGefördert im Rahmen des Projekts DEALger
dc.language.isoengeng
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.titleOn the Expressive Power of Stateless Ordered Restart-Delete Automataeng
dc.typeAufsatz
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
dc.relation.doidoi:10.1007/s00224-020-10028-3
dc.subject.swdAutomationger
dc.subject.swdRestart-Automatger
dc.subject.swdKontextfreie Spracheger
dc.type.versionpublishedVersion
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 in this item

Thumbnail
Name:
Otto2021_Article_OnTheExpressi ...
Size:
1.475Mb
Format:
PDF
View/Open
Thumbnail
Name:
license_rdf
Size:
908bytes
Format:
application/rdf+xml
View/Open

This item appears in the following Collection(s)

Show simple item record

Namensnennung 4.0 International
Except where otherwise noted, this item's license is described as Namensnennung 4.0 International