Nie jesteś zalogowany |
On the expressibility of copyless cost register automata
- Prelegent(ci)
- Filip Mazowiecki
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 13 maja 2015 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed as a new computational model. We study the properties and expressiveness of the copyless CRA. Our studies lead to results that copyless CRA do not have good closure properties because they are not closed under reverse operation. To find a better class we impose restrictions on copyless CRA, which ends successfully with a new computational model that enjoys good closure properties.
We also introduce a new logic called maximal partition logic (MP). In contrast to the previous approaches (i.e., weighted logics), MP is based on a new set of regular quantifiers that partition a word into maximal subwords, compute the output of a subformula over each subword separately, and then aggregate these outputs with a semiring operation. We study the expressiveness of MP and compare it with weighted logics. Furthermore, we show that MP is a logical characterization of the restricted fragment of copyless CRA.
We also introduce a new logic called maximal partition logic (MP). In contrast to the previous approaches (i.e., weighted logics), MP is based on a new set of regular quantifiers that partition a word into maximal subwords, compute the output of a subformula over each subword separately, and then aggregate these outputs with a semiring operation. We study the expressiveness of MP and compare it with weighted logics. Furthermore, we show that MP is a logical characterization of the restricted fragment of copyless CRA.
