http://sedici.unlp.edu.ar:80/handle/10915/65159 Tue, 10 Nov 2026 20:21:44 GMT 2026-11-10T20:21:44Z http://sedici.unlp.edu.ar:80/handle/10915/65164 Objeto de conferencia Simposio Latinoamericano de Teoría Computacional (SLTC) - JAIIO 46 (Córdoba, 2017). Abstract—We study synchronization games on planar automata. We prove that recognizing the planar games that can be won by the synchronizer is a co-NP hard problem. We prove some additional results indicating that planar games are as hard as nonplanar games. Those results amount to show that planar automata are representative of the intricacies of automata synchronization. Sun, 01 Jan 2017 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/65164 2017-01-01T00:00:00Z Abstract—We study synchronization games on planar automata. We prove that recognizing the planar games that can be won by the synchronizer is a co-NP hard problem. We prove some additional results indicating that planar games are as hard as nonplanar games. Those results amount to show that planar automata are representative of the intricacies of automata synchronization. http://sedici.unlp.edu.ar:80/handle/10915/65163 Objeto de conferencia Simposio Latinoamericano de Teoría Computacional (SLTC) - JAIIO 46 (Córdoba, 2017). In this paper we present a series of theorems that allow to establish strategies for the calculation of invariant assertions, such as the Dijkstra’s Hk(Post), or the weakest precondition of the loop. A criterion is also shown for calculating the termination condition of a loop. As in the integrals calculus, the strategies proposed here to perform the calculation of an invariant, will depend on the shape of the loop with which it is working, particularly will work with for-type loops with or without early termination due to a sentry. Sun, 01 Jan 2017 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/65163 2017-01-01T00:00:00Z In this paper we present a series of theorems that allow to establish strategies for the calculation of invariant assertions, such as the Dijkstra’s Hk(Post), or the weakest precondition of the loop. A criterion is also shown for calculating the termination condition of a loop. As in the integrals calculus, the strategies proposed here to perform the calculation of an invariant, will depend on the shape of the loop with which it is working, particularly will work with for-type loops with or without early termination due to a sentry. http://sedici.unlp.edu.ar:80/handle/10915/65162 Objeto de conferencia Simposio Latinoamericano de Teoría Computacional (SLTC) - JAIIO 46 (Córdoba, 2017). In this work we study pebble automata. Those automata constitute an infinite hierarchy of discrete models of computation. The hierarchy begins at the level of finite state automata (0-pebble automata) and approaches the model of onetape Turing machines. Thus, it can be argued that it is a complete hierarchy that covers, in a continuous way, all the models of automata that are important in the theory of computation. We investigate the use of this hierarchy as a narrative for the teaching of automata theory. We also investigate some fundamental questions concerning the power of pebble automata. Sun, 01 Jan 2017 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/65162 2017-01-01T00:00:00Z In this work we study pebble automata. Those automata constitute an infinite hierarchy of discrete models of computation. The hierarchy begins at the level of finite state automata (0-pebble automata) and approaches the model of onetape Turing machines. Thus, it can be argued that it is a complete hierarchy that covers, in a continuous way, all the models of automata that are important in the theory of computation. We investigate the use of this hierarchy as a narrative for the teaching of automata theory. We also investigate some fundamental questions concerning the power of pebble automata. http://sedici.unlp.edu.ar:80/handle/10915/65161 Objeto de conferencia Simposio Latinoamericano de Teoría Computacional (SLTC) - JAIIO 46 (Córdoba, 2017). In this work we study the intrinsic complexity of elimination algorithms in effective algebraic geometry and we focus our attention to elimination algorithms produced within the object–oriented paradigm. To this end, we describe a new computation model called quiz game (introduced in [1]) which models the notions of information hiding (due to Parnas, see [2]) and non–functional requirements (e.g. robustness) among other important concepts in software engineering. This characteristic distinguish our model from classical computation models such as the Turing machine or algebraic models. We illustrate our computation model with a non–trivial complexity lower bound for the identity function of polynomials. We show that any object–oriented (and robust) implementation of the identity function of polynomials is necessarily inefficient compared with a trivial implementation of this function. This result shows an existing synergy between Software Engineering and Algebraic Complexity Theory. Sun, 01 Jan 2017 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/65161 2017-01-01T00:00:00Z In this work we study the intrinsic complexity of elimination algorithms in effective algebraic geometry and we focus our attention to elimination algorithms produced within the object–oriented paradigm. To this end, we describe a new computation model called quiz game (introduced in [1]) which models the notions of information hiding (due to Parnas, see [2]) and non–functional requirements (e.g. robustness) among other important concepts in software engineering. This characteristic distinguish our model from classical computation models such as the Turing machine or algebraic models. We illustrate our computation model with a non–trivial complexity lower bound for the identity function of polynomials. We show that any object–oriented (and robust) implementation of the identity function of polynomials is necessarily inefficient compared with a trivial implementation of this function. This result shows an existing synergy between Software Engineering and Algebraic Complexity Theory. http://sedici.unlp.edu.ar:80/handle/10915/65160 Objeto de conferencia Simposio Latinoamericano de Teoría Computacional (SLTC) - JAIIO 46 (Córdoba, 2017). There are different algebraic structures that one can use to model notions of computation. The most well-known are monads, but lately, applicative functors have been gaining popularity. These two structures can be understood as instances of the unifying notion of monoid in a monoidal category. When dealing with non-determinism, it is usual to extend monads and applicative functors with additional structure. However, depending on the desired non-determinism, there are different options of interaction between the existing and the additional structure. This article studies one of those options, which is captured algebraically by dioids. We generalise dioids to dioid categories and show how dioids in such a category model nondeterminism in monads and applicative functors. Moreover, we study the construction of free dioids in a programming context. Sun, 01 Jan 2017 00:00:00 GMT http://sedici.unlp.edu.ar:80/handle/10915/65160 2017-01-01T00:00:00Z There are different algebraic structures that one can use to model notions of computation. The most well-known are monads, but lately, applicative functors have been gaining popularity. These two structures can be understood as instances of the unifying notion of monoid in a monoidal category. When dealing with non-determinism, it is usual to extend monads and applicative functors with additional structure. However, depending on the desired non-determinism, there are different options of interaction between the existing and the additional structure. This article studies one of those options, which is captured algebraically by dioids. We generalise dioids to dioid categories and show how dioids in such a category model nondeterminism in monads and applicative functors. Moreover, we study the construction of free dioids in a programming context.