On Shrinking Restarting Automata of Window Size One and Two
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10408540" target="_blank" >RIV/00216208:11320/19:10408540 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-030-24886-4_10" target="_blank" >https://doi.org/10.1007/978-3-030-24886-4_10</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-24886-4_10" target="_blank" >10.1007/978-3-030-24886-4_10</a>
Alternative languages
Result language
angličtina
Original language name
On Shrinking Restarting Automata of Window Size One and Two
Original language description
Here we study the expressive power of shrinking RWW- and RRWW-automata the window size of which is just one or two. We show that for shrinking RRWW-automata that are nondeterministic, window size one suffices, while for nondeterministic shrinking RWW-automata, we already need window size two to accept all growing context-sensitive languages. In the deterministic case, shrinking RWW- and RRWW-automata of window size one accept only regular languages, while those of window size two characterize the Church-Rosser languages. In addition, we study shrinking RWW- and RRWW-automata of window size one that are monotone.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Developments in Language Theory 23rd International Conference, DLT 2019, Warsaw, Poland, August 5–9, 2019
ISBN
978-3-030-24885-7
ISSN
0302-9743
e-ISSN
—
Number of pages
14
Pages from-to
140-153
Publisher name
Springer Nature Switzerland AG
Place of publication
Cham, Switzerland
Event location
Varšava
Event date
Aug 5, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—