On a reachability set of automaton counter machines

Autor: E. V. Kuzmin, D. J. Chalyy

Publikováno v: Моделирование и анализ информационных систем, Vol 17, Iss 1, Pp 52-64 (2010)

Properties of automaton counter machines are investigated. We prove that reachability sets of automaton one-counter machines are semilinear. An algorithm of construction of these semilinear reachability sets is resultexl. Besides, it is shown that re

Externí odkaz: https://doaj.org/article/ac8a39bdc3c94f91a244f3156cd80589

Semilinear Representations for Series-Parallel Atomic Congestion Games

Autor: Bertrand, Nathalie, Markey, Nicolas, Sadhukhan, Suman, Sankur, Ocan

Publikováno v: Leibniz International Proceedings in Informatics
FSTTCS 2022-42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
FSTTCS 2022-42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2022, Chennai, France. pp.1-20, ⟨10.4230/LIPIcs.FSTTCS.2022.32⟩

We consider atomic congestion games on series-parallel networks, and study the structure of the sets of Nash equilibria and social local optima on a given network when the number of players varies. We establish that these sets are definable in Presbu

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::39d5a1dfb10a4a6d3fff7472b2799b95

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Constraint satisfaction and semilinear expansions of addition over the rationals and the reals

Autor: Peter Jonsson, Johan Thapper

Publikováno v: Journal of Computer and System Sciences
Journal of Computer and System Sciences, Elsevier, 2016, 82 (5), pp.912-928. ⟨10.1016/j.jcss.2016.03.002⟩

A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals, or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theor

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6e7caf4e810eca7db7a9155124780285
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-128917

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Autor: Cadilhac, Michaël

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture

Externí odkaz: http://hdl.handle.net/1866/10485