On the expressibility of copyless cost register automata.
Filip Mazowiecki, Cristian Riveros · arXiv (Cornell University) · 2015
Cost register automata (CRA) were proposed by Alur et all as an alternative model for weighted automata. In hope of finding decidable subclasses of CRA, they proposed to restrict their model with the copyless restriction but nothing is really know about the structure or properties of this new computational model called copyless CRA. In this paper we study the properties and expressiveness of copyless CRA. We propose a normal form for copyless CRA and we study the properties of a special group of registers (called stable registers). Furthermore, we find that copyless CRA do not have good closure properties since we show that they are not closed under reverse operation. Finally, we propose a subclass of copyless CRA and we show that this subclass is closed under regular-lookahead.