Power of S-kR-RRWW-automata
Power of S-\(k\)R-RRWW-automata
Authors: Petr Hoffmann;
doi: 10.3233/fi-2015-1145
Power of S-kR-RRWW-automata
Abstract
Single k-reversible restarting automata are a special version of restarting automata which can be effectively learned from samples. We show that their power lies between GCSL and CSL. We show that their subclasses form an infinite hierarchy of classes of languages with respect to the reversibility level k and we also show that limiting types of allowed rewrites lowers the power of the model. Finally, we study their relation to strictly locally testable restarting automata.
Related Organizations
- Charles University Czech Republic
Keywords
Formal languages and automata
Formal languages and automata
1 Research products, page 1 of 1
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
citations
Citations provided by BIP!
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
popularity
Popularity provided by BIP!
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
0
Average
Average
Average
