- Todo
- Actas de conferencias
- Biomecánica
- Ciencias de la Tierra
- Ciencias humanas y sociales
- Ciencias sanitarias
- Física
- Informática y matemáticas aplicadas
- Matemáticas
- Mecánica
- Medioambiente
Informática y matemáticas aplicadas
ARIMA
[Revue africaine de recherche en informatique et mathématiques appliquées]
ARIMA
Revue africaine de recherche en informatique et mathématiques appliquées
ARIMA nació en 2002 de una colaboración científica Norte/Sur llevada a cabo a raíz de las actividades del Coloquio Africano para la Investigación en Informática y Matemáticas Aplicadas (CARI). La revista publica regularmente, en francés e inglés, los resultados de las investigaciones resultantes de estas cooperaciones.
- Director de publicación: Maurice Tchuenté
- Redactores en jefe: Nabil Gmati ; Mathieu Roche ; Tayou Djamegni Clémentin
- Tipo de soporte: electrónico
- Periodicidad: sobre la marcha
- Año de creación: 2002
- Fecha de publicación en Episciences: 2016
- eISSN: 1638-5713
- Disciplinas: Informática y Matemáticas Aplicadas
- Idiomas de publicación: inglés, francés
- Procedimiento de evaluación: evaluación simple ciega
- CC BY 4.0 licence
- Editor: African Society in Digital Science
- Dirección postal: Department of Mathematics and Computer Science, Faculty of Science, University of Dschang, P.O. Box 96 Dschang
- País: Camerún
- Contacto: arima AT episciences.org
Últimos artículos
Prise en compte du temps et des catégories d'item dans l'estimation des influences sociales implicites pour l'amélioration des systèmes de recommandation basés sur la confiance.
De nos jours, les plateformes d’e-commerce, de streaming et de réseaux sociaux jouent un rôle important dans notre quotidien. Cependant, l’ajout toujours croissant d’éléments sur ces plateformes (articles sur Amazon, vidéos sur Netflix et YouTube, publications sur Facebook et Instagram) rend difficile pour les utilisateurs de sélectionner les éléments qui les intéressent. L'intégration de systèmes de recommandation dans ces plateformes vise à proposer à chaque utilisateur une petite liste d'éléments correspondant à ses préférences. Pour améliorer les performances de ces systèmes de recommandation, certains travaux de la littérature intègrent une confiance explicite ou implicite entre les utilisateurs de la plateforme via des systèmes de recommandation basés sur la confiance. En effet, nombre de ces travaux reposent sur une confiance explicite, lorsque chaque utilisateur désigne ceux en qui il a confiance dans la plateforme. Mais ces informations sont rares sur la plupart des plateformes du monde réel. Ainsi, d'autres travaux proposent d'estimer la confiance implicite que chaque utilisateur peut accorder à un autre. Cependant, les travaux qui estiment la confiance implicite ne prennent pas en compte la dynamique temporelle des actions passées des utilisateurs et encore moins le fait qu'un utilisateur peut en influencer un autre sur une catégorie d'item et pas sur une autre. Dans cet article, nous proposons des stratégies sensibles au temps et au contenu pour estimer l'influence sociale d'un utilisateur sur un autre. La confiance implicite qui en résulte, consciente du temps et du contenu, est intégrée aux systèmes de recommandation basés sur la confiance, construits sur les K-Nearest Neighbours (KNN) et les techniques basées sur les graphiques. Les expériences réalisées pour les prédictions de notation avec KNN et les recommandations Top-N avec le modèle Graph montrent que la confiance implicite consciente du temps et du contenu permet d'améliorer les performances du KNN selon la métrique RMSE de 7% et 10%, et les performances du modèle graphique selon la métrique NDCG@10 de 59% et 08% respectivement sur les jeux de données Ciao et Epinions.
Nzekon Nzeko'o, Armel Jacques
March 23, 2025
Read article
Clustering-based Graph Numbering using Execution Traces for Cache Misses Reduction in Graph Analysis Applications
Social graph analysis is generally based on a local exploration of the underlying graph. That is, the analysis of a node of the graph is often done after having analyzed nodes located in its vicinity. However, over the time, networks are bound to grow with the addition of new members, which inevitably leads to the enlargement of the corresponding graphs. At this level we therefore have a problem because more the size of the graph increases, more the execution time of graph analysis applications too. This is due to the very large number of nodes that will need to be treated. Some recent work in-faces this problem by exploiting the properties of social networks such as the community structure to renumber the nodes of the graph in order to reduce cache misses. Reducing cache misses in an application allows to reduce the execution time of this application. In this paper, we argue that combining existing graph ordering with a new numbering that exploit execution traces analysis can allow to improve cache misses reduction and hence execution time reduction. The idea is to build graph numbering using execution traces of graph analysis applications and then combine it with an existing graph numbering (such as cn-order). To build this new ordering, we define a new distance and then used it to analyse execution traces with well known clustering algorithms K-means (for Kmeans-order) and hierarchical clustering (for cl-hier-order). Experiments on a user machine (dual-core) and four cores of Grid'5000 node (Neowise) show that this combination improves slightly existing graph ordering (cn-order, numbaco, rabbit and gorder) in almost all the cases (the two cores of dual-core, all the four cores of neowise), with PageRank graph application and astro-ph dataset. For example, on neowise with one thread and Astro-ph dataset, the best performance is given with the combination kmeans-order_cn-order which allows to reduce by 42.59% the cache misses (compared to the second numbaco with 40.79%) and therefore by 7.27 % the time of execution (compared to 6.89% for the second numbaco).
Mogo Wafo, Régis Audran
March 08, 2025
Read article
Informática y matemáticas aplicadas
Compositionality
Compositionality
Fundada en 2017, Compositionality acoge artículos de investigación en inglés en el campo de las matemáticas de la composición en todas las disciplinas. La revista está publicada por la Compositionality Charitable Incorporated Organisation.
- Director de publicación: John Baez
- Redactores jefe: Aleks Kissinger ; Joachim Kock
- Tipo de soporte: electrónico
- Periodicidad: anual
- Año de creación: 2017
- Fecha de publicación en Episciences: 2024
- eISSN: 2631-4444
- Disciplinas: matemáticas, cálculo, lógica, física, química, ingeniería, lingüística, cognición
- Idiomas de publicación: inglés
- Procedimiento de evaluación: evaluación simple ciega
- Licencia CC BY 4.0
- Editor: Compositionality Charitable Incorporated Organisation
- Dirección postal: 108 Kennington Road, Kennington, Oxford, OX1 5PE
- País: Reino Unido
- Contacto: compositionality AT episciences.org
Últimos artículos
Information Decomposition Diagrams Applied beyond Shannon Entropy: A Generalization of Hu's Theorem
In information theory, one major goal is to find useful functions that summarize the amount of information contained in the interaction of several random variables. Specifically, one can ask how the classical Shannon entropy, mutual information, and higher interaction information relate to each other. This is answered by Hu's theorem, which is widely known in the form of information diagrams: it relates shapes in a Venn diagram to information functions, thus establishing a bridge from set theory to information theory. In this work, we view random variables together with the joint operation as a monoid that acts by conditioning on information functions, and entropy as a function satisfying the chain rule of information. This abstract viewpoint allows to prove a generalization of Hu's theorem. It applies to Shannon and Tsallis entropy, (Tsallis) Kullback-Leibler Divergence, cross-entropy, Kolmogorov complexity, submodular information functions, and the generalization error in machine learning. Our result implies for Chaitin's Kolmogorov complexity that the interaction complexities of all degrees are in expectation close to Shannon interaction information. For well-behaved probability distributions on increasing sequence lengths, this shows that the per-bit expected interaction complexity and information asymptotically coincide, thus showing a strong bridge between algorithmic and classical information theory.
Lang, Leon
January 30, 2025
Read article
Homotopy Theoretic and Categorical Models of Neural Information Networks
In this paper we develop a novel mathematical formalism for the modeling of neural information networks endowed with additional structure in the form of assignments of resources, either computational or metabolic or informational. The starting point for this construction is the notion of summing functors and of Segal's Gamma-spaces in homotopy theory. The main results in this paper include functorial assignments of concurrent/distributed computing architectures and associated binary codes to networks and their subsystems, a categorical form of the Hopfield network dynamics, which recovers the usual Hopfield equations when applied to a suitable category of weighted codes, a functorial assignment to networks of corresponding information structures and information cohomology, and a cohomological version of integrated information.
Manin, Yuri
September 06, 2024
Read article
Informática y matemáticas aplicadas
DMTCS
[Discrete Mathematics & Theoretical Computer Science]
DMTCS
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science (DMTCS) es una revista con comité de lectura creada en 1997. Respaldada por la asociación DMTCS, publica artículos de investigación en inglés, en los campos de las matemáticas discretas y la informática teórica, en particular en la intersección de estas dos disciplinas.
- Director de publicación: Jens Gustedt
- Redactores y redactora en jefe: Christoph Haase, Dieter Rautenbach, Sergi Elizalde y Hadas Shachnai
- Tipo de soporte: electrónico
- Periodicidad: sobre la marcha
- Año de creación: 1997
- Fecha de publicación en Episciences: 2016
- eISSN: 1365-8050
- Disciplinas: matemáticas, informática
- Idiomas de publicación: inglés
- Procedimiento de evaluación: evaluación simple ciega
- CC BY 4.0 licence
- Editor: Association DMTCS
- Dirección postal: c/o Jens Gustedt, 67A avenue Jean-Jaurès, 67100 Strasbourg
- País: Francia
- Contacto: dmtcs AT episciences.org
Últimos artículos
A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.
Pilipczuk, Marcin
March 18, 2025
Read article
Treewidth 2 in the Planar Graph Product Structure Theorem
We prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible: for any $c \in \mathbb{N}$, there is a planar graph $G$ such that for any tree $T$ and graph $H$ with $\text{tw}(H) \leqslant 2$, $G$ is not contained in $H \boxtimes T \boxtimes K_c$.
Distel, Marc
March 17, 2025
Read article
Actas de conferencias
Informática y matemáticas aplicadas
ENTICS
[Electronic Notes in Theoretical Informatics and Computer Science]
ENTICS
Electronic Notes in Theoretical Informatics and Computer Science
ENTICS, Electronic Notes in Theoretical Informatics and Computer Science, creada en 2022, publica en inglés actas de conferencias y talleres de informática teórica.
- Director de publicación: Bruno Sportisse
- Redactor en jefe: Michael Mislove
- Tipo de soporte: electrónico
- Periodicidad: sobre la marcha
- Año de creación: 2022
- Fecha de publicación en Episciences: 2023
- eISSN: 2969-2431
- Disciplinas: informática teórica
- Idiomas de publicación: inglés
- Procedimiento de evaluación: evaluación simple ciega
- Licence CC BY 4.0
- Editor: Inria
- Dirección postal: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
- País: Francia
- Contacto: entics AT episciences.org
Últimos artículos
Implicit automata in {\lambda}-calculi III: affine planar string-to-string functions
We prove a characterization of first-order string-to-string transduction via $\lambda$-terms typed in non-commutative affine logic that compute with Church encoding, extending the analogous known characterization of star-free languages. We show that every first-order transduction can be computed by a $\lambda$-term using a known Krohn-Rhodes-style decomposition lemma. The converse direction is given by compiling $\lambda$-terms into two-way reversible planar transducers. The soundness of this translation involves showing that the transition functions of those transducers live in a monoidal closed category of diagrams in which we can interpret purely affine $\lambda$-terms. One challenge is that the unit of the tensor of the category in question is not a terminal object. As a result, our interpretation does not identify $\beta$-equivalent terms, but it does turn $\beta$-reductions into inequalities in a poset-enrichment of the category of diagrams.
Pradic, Cécilia
December 11, 2024
Read article
Cost-sensitive computational adequacy of higher-order recursion in synthetic domain theory
We study a cost-aware programming language for higher-order recursion dubbed $\textbf{PCF}_\mathsf{cost}$ in the setting of synthetic domain theory (SDT). Our main contribution relates the denotational cost semantics of $\textbf{PCF}_\mathsf{cost}$ to its computational cost semantics, a new kind of dynamic semantics for program execution that serves as a mathematically natural alternative to operational semantics in SDT. In particular we prove an internal, cost-sensitive version of Plotkin's computational adequacy theorem, giving a precise correspondence between the denotational and computational semantics for complete programs at base type. The constructions and proofs of this paper take place in the internal dependent type theory of an SDT topos extended by a phase distinction in the sense of Sterling and Harper. By controlling the interpretation of cost structure via the phase distinction in the denotational semantics, we show that $\textbf{PCF}_\mathsf{cost}$ programs also evince a noninterference property of cost and behavior. We verify the axioms of the type theory by means of a model construction based on relative sheaf models of SDT.
Niu, Yue
December 11, 2024
Read article
Informática y matemáticas aplicadas
FI
[Fundamenta Informaticae]
FI
Fundamenta Informaticae
Fundada en 1977, Fundamenta Informaticae es una revista científica con comité de lectura que cubre todas las áreas de la informática, con un enfoque particular en los fundamentos teóricos. La revista se publica en la serie IV de los Annales Societatis Mathematicae Polonae por la Sociedad Matemática Polaca.
- Director de publicación: Prof. Jacek Miękisz
- Redactor en jefe: Bartek Klin
- Tipo de soporte: papel y electrónico
- Periodicidad: 3 a 4 volúmenes al año
- Año de creación: 1977
- Fecha de publicación en Episciences: 2020
- eISSN: 1875-8681
- Disciplinas: informática
- Idiomas de publicación: inglés
- Procedimiento de evaluación: evaluación simple ciega
- CC BY 4.0 licence
- Editor: Polish Mathematical Society
- Dirección postal: ul. Śniadeckich 8, 00-656 Warszawa
- País: Polonia
- Contacto: fi AT episciences.org
Últimos artículos
Proving Confluence in the Confluence Framework with CONFident
This article describes the *Confluence Framework*, a novel framework for proving and disproving confluence using a divide-and-conquer modular strategy, and its implementation in CONFident. Using this approach, we are able to automatically prove and disprove confluence of *Generalized Term Rewriting Systems*, where (i) only selected arguments of function symbols can be rewritten and (ii) a rather general class of conditional rules can be used. This includes, as particular cases, several variants of rewrite systems such as (context-sensitive) *term rewriting systems*, *string rewriting systems*, and (context-sensitive) *conditional term rewriting systems*. The divide-and-conquer modular strategy allows us to combine in a proof tree different techniques for proving confluence, including modular decompositions, checking joinability of (conditional) critical and variable pairs, transformations, etc., and auxiliary tasks required by them, e.g., joinability of terms, joinability of conditional pairs, etc.
Gutiérrez, Raúl
November 10, 2024
Read article
On Complexity Bounds and Confluence of Parallel Term Rewriting
We revisit parallel-innermost term rewriting as a model of parallel computation on inductive data structures and provide a corresponding notion of runtime complexity parametric in the size of the start term. We propose automatic techniques to derive both upper and lower bounds on parallel complexity of rewriting that enable a direct reuse of existing techniques for sequential complexity. Our approach to find lower bounds requires confluence of the parallel-innermost rewrite relation, thus we also provide effective sufficient criteria for proving confluence. The applicability and the precision of the method are demonstrated by the relatively light effort in extending the program analysis tool AProVE and by experiments on numerous benchmarks from the literature.
Baudon, Thaïs
November 10, 2024
Read article
Ciencias humanas y sociales
Informática y matemáticas aplicadas
JDMDH
[Journal of Data Mining and Digital Humanities]
JDMDH
Journal of Data Mining and Digital Humanities
Creada en 2014, Journal of Data Mining and Digital Humanities (JDMDH) se encuentra en la intersección de la prospección de datos y las humanidades digitales. Los artículos publicados, en inglés o en francés, se refieren tanto a la extracción y gestión de conocimientos (análisis de redes, extracción de información, web semántica, análisis de preferencias, aprendizaje automático) como a las ciencias humanas y sociales (históricas, políticas, lingüísticas, sociológicas, geográficas, de comunicación y archivo) en la era digital.
- Director de publicación: Bruno Sportisse
- Redactores en jefe: Richi Nayak, Laurent Romary y Nicolas Turenne
- Tipo de soporte: electrónico
- Periodicidad: sobre la marcha
- Año de creación: 2014
- Fecha de publicación en Episciences: 2014
- eISSN: 2416-5999
- Disciplinas: humanidades digitales
- Idiomas de publicación: inglés, francés
- Procedimiento de evaluación: evaluación simple ciega
- CC BY 4.0 licence
- Editor: Inria
- Dirección postal: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
- País: Francia
- Contacto: jdmdh AT episciences.org
Últimos artículos
Out of Context! Managing the Limitations of Context Windows in ChatGPT-4o Text Analyses
In recent years, large language model (LLM) applications have surged in popularity, and academia has followed suit. Researchers frequently seek to automate text annotation - often a tedious task – and, to some extent, text analysis. Notably, popular LLMs such as ChatGPT have been studied as both research assistants and analysis tools, revealing several concerns regarding transparency and the nature of AI-generated content. This study assesses ChatGPT’s usability and reliability for text analysis – specifically keyword extraction and topic classification – within an “out-of-the-box” zero-shot or few-shot context, emphasizing how the size of the context window and varied text types influence the resulting analyses. Our findings indicate that text type and the order in which texts are presented both significantly affect ChatGPT’s analysis. At the same time, context-building tends to be less problematic when analyzing similar texts. However, lengthy texts and documents pose serious challenges: once the context window is exceeded, “hallucinated” results often emerge. While some of these issues stem from the core functioning of LLMs, some can be mitigated through transparent research planning.
Mervaala, Erkki
March 07, 2025
Read article
Comparing Human-Perceived Cluster Characteristics through the Lens of CIPHE: Measuring Coherence beyond Keywords
A frequent problem in document clustering and topic modeling is the lack of ground truth. Models are typically intended to reflect some aspect of how human readers view texts (the general theme, sentiment, emotional response, etc), but it can be difficult to assess whether they actually do. The only real ground truth is human judgement. To enable researchers and practitioners to collect such judgement in a cost-efficient standardized way, we have developed the crowdsourcing solution CIPHE -- Cluster Interpretation and Precision from Human Exploration. CIPHE is an adaptable framework which systematically gathers and evaluates data on the human perception of a set of document clusters where participants read sample texts from the cluster. In this article, we use CIPHE to study the limitations that keyword-based methods pose in topic modeling coherence evaluation. Keyword methods, including word intrusion, are compared with the outcome of the thorougher CIPHE on scoring and characterizing clusters. The results show how the abstraction of keywords skews the cluster interpretation for almost half of the compared instances, meaning that many important cluster characteristics are missed. Further, we present a case study where CIPHE is used to (a) provide insights into the UK news domain and (b) find out how the evaluated clustering model should be tuned to better suit the intended application. The experiments provide evidence that CIPHE characterizes clusters in a predictable manner and has the potential to be a valuable framework for using human evaluation in the pursuit of nuanced research aims.
Eklund, Anton
March 07, 2025
Read article
Informática y matemáticas aplicadas
JIPS
[Journal d’Interaction Personne-Système]
JIPS
Journal d’Interaction Personne-Système
Creada en 2008 por la Asociación Francófona para la Interacción Humano-Máquina, Journal d’Interaction Personne-Système (JIPS) sucedió a la Revue d’Interaction Homme-Machine (RIHM), fundada en 1997 y activa hasta 2007 (luego se convirtió en la Revue des Interactions Humaines Médiatisées).
JIPS dejó de publicarse en abril de 2022; los artículos publicados permanecen accesibles en el sitio web de la revista.
- Directora de publicación: Sophie Dupuy-Chessa
- Tipo de soporte: electrónico
- Estado de la colección: 2010-2020
- Año de creación: 2008
- Fecha de publicación en Episciences: 2014
- eISSN: 2418-1838
- Disciplinas: ingeniería, tecnologías, ciencias cognitivas
- Idiomas de publicación: inglés, francés
- CC BY 4.0 licence
- Editor: Association Francophone d’Interaction Homme-Machine (AFIHM)
- Dirección postal: 385 rue de la Bibliothèque, 38041 Grenoble Cedex
- País: Francia
- Contacto: presidence AT afihm.org
Últimos artículos
Informática y matemáticas aplicadas
JoDaKISS
[Journal of Data- and Knowledge-integrated Simulation Science]
JoDaKISS
Journal of Data- and Knowledge-integrated Simulation Science
Próximamente
Journal of Data- and Knowledge-integrated Simulation Science (JoDaKISS) es una revista internacional multidisciplinar dedicada a apoyar y hacer avanzar la ciencia de la simulación mediante la publicación de datos y software de alta calidad para simulaciones científicas por ordenador. La publica el Centro de Ciencias de la Simulación de Stuttgart (SC SimTech, Universidad de Stuttgart, Alemania).
- Director de publicación: Holger Steeb
- Consejo de redacción: Bernd Flemisch, Dominik Göddeke, Jeroen Hanselman, Jan Heiland, Sibylle Hermann, Melanie Herschel, Timo Koch, Holger Steeb
- Tipo de soporte: electrónico
- Periodicidad: sobre la marcha
- Año de creación: 2024
- eISSN: 2944-7666
- Disciplinas: ciencia de la simulación, experimentos ricos en datos, simulaciones numéricas directas
- Idiomas de publicación: inglés
- Procedimiento de evaluación: evaluación simple ciega
- Licencia CC BY 4.0
- Editor: Stuttgart Center of Simulation Science (SC SimTech)
- Dirección postal: Pfaffenwaldring 5a, 70569 Stuttgart
- País: Alemania
- Contacto: jodakiss AT episciences.org
Informática y matemáticas aplicadas
LMCS
[Logical Methods in Computer Science]
LMCS
Logical Methods in Computer Science
Logical Methods in Computer Science (LMCS) publica regularmente artículos de investigación en inglés sobre áreas teóricas y prácticas de la informática que involucran métodos lógicos, tomados en un sentido amplio. Creada en 2014, la revista es publicada por Logical Methods in Computer Science eV, una organización sin fines de lucro cuyo objetivo es facilitar la difusión de resultados científicos relacionados con la lógica en informática.
- Director de publicación: Lars Birkedal
- Redactor en jefe: Stefan Milius
- Tipo de soporte: electrónico
- Periodicidad: sobre la marcha
- Año de creación: 2014
- Fecha de publicación en Episciences: 2015
- eISSN: 1860-5974
- Disciplinas: métodos lógicos
- Idiomas de publicación: inglés
- Procedimiento de evaluación: evaluación simple ciega
- CC BY 4.0 licence
- Editor: Logical Methods in Computer Science e.V.
- País: Alemania
- Contacto: lmcs AT episciences.org
Últimos artículos
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
We study the enumeration of answers to Unions of Conjunctive Queries (UCQs) with optimal time guarantees. More precisely, we wish to identify the queries that can be solved with linear preprocessing time and constant delay. Despite the basic nature of this problem, it was shown only recently that UCQs can be solved within these time bounds if they admit free-connex union extensions, even if all individual CQs in the union are intractable with respect to the same complexity measure. Our goal is to understand whether there exist additional tractable UCQs, not covered by the currently known algorithms. As a first step, we show that some previously unclassified UCQs are hard using the classic 3SUM hypothesis, via a known reduction from 3SUM to triangle listing in graphs. As a second step, we identify a question about a variant of this graph task that is unavoidable if we want to classify all self-join-free UCQs: is it possible to decide the existence of a triangle in a vertex-unbalanced tripartite graph in linear time? We prove that this task is equivalent in hardness to some family of UCQs. Finally, we show a dichotomy for unions of two self-join-free CQs if we assume the answer to this question is negative. In conclusion, this paper pinpoints a computational barrier in the form of a single decision problem that is key to advancing our understanding of the enumeration complexity of many UCQs. Without a breakthrough for unbalanced triangle detection, we have no hope of finding an efficient algorithm for additional unions of two self-join-free CQs. On the other hand, a sufficiently efficient unbalanced triangle detection algorithm can be turned into an efficient algorithm for a family of UCQs currently not known to be tractable.
Bringmann, Karl
March 27, 2025
Read article
Characterising memory in infinite games
This paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (LICS 2022) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs: an objective is positional if and only if it admits well-ordered monotone universal graphs. We extend Ohlmann's characterisation to encompass (finite or infinite) memory upper bounds. We prove that objectives admitting optimal strategies with $\varepsilon$-memory less than $m$ (a memory that cannot be updated when reading an $\varepsilon$-edge) are exactly those which admit well-founded monotone universal graphs whose antichains have size bounded by $m$. We also give a characterisation of chromatic memory by means of appropriate universal structures. Our results apply to finite as well as infinite memory bounds (for instance, to objectives with finite but unbounded memory, or with countable memory strategies). We illustrate the applicability of our framework by carrying out a few case studies, we provide examples witnessing limitations of our approach, and we discuss general closure properties which follow from our results.
Casares, Antonio
March 24, 2025
Read article
Informática y matemáticas aplicadas
MNA
[Mathematical Neuroscience and Applications]
MNA
Mathematical Neuroscience and Applications
Creada en 2021, la revista Mathematical Neuroscience and Applications (MNA) se interesa por la modelización y el análisis matemático en todas las áreas de la neurociencia, es decir, el estudio del sistema nervioso y sus disfunciones. Es la continuación del Journal of Mathematical Neuroscience (2011-2021), publicado anteriormente por Springer. La revista acepta artículos en inglés.
- Director de publicación: Bruno Sportisse
- Redactor en jefe: Olivier Faugeras
- Tipo de soporte: electrónico
- Periodicidad: anual
- Año de creación: 2021
- Fecha de publicación en Episciences: 2021
- eISSN: 2801-0159
- Disciplinas: neurociencia
- Idiomas de publicación: inglés
- Procedimiento de evaluación: evaluación simple ciega
- CC BY 4.0 licence
- Editor: Inria
- Dirección postal: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
- País: Francia
- Contacto: mna AT episciences.org
Últimos artículos
A Quasi-Stationary Approach to Metastability in a System of Spiking Neurons with Synaptic Plasticity
After reviewing the behavioral studies of working memory and of the cellular substrate of the latter, we argue that metastable states constitute candidates for the type of transient information storage required by working memory. We then present a simple neural network model made of stochastic units whose synapses exhibit short-term facilitation. The Markov process dynamics of this model was specifically designed to be analytically tractable, simple to simulate numerically and to exhibit a quasi-stationary distribution (QSD). Since the state space is finite this QSD is also a Yaglom limit, which allows us to bridge the gap between quasi-stationarity and metastability by considering the relative orders of magnitude of the relaxation and absorption times. We present first analytical results: characterization of the absorbing region of the Markov process, irreducibility outside this absorbing region and consequently existence and uniqueness of a QSD. We then apply Perron-Frobenius spectral analysis to obtain any specific QSD, and design an approximate method for the first moments of this QSD when the exact method is intractable. Finally we use these methods to study the relaxation time toward the QSD and establish numerically the memorylessness of the time of extinction.
André, Morgan
January 02, 2025
Read article
A mean-field model of Integrate-and-Fire neurons: non-linear stability of the stationary solutions
We investigate a stochastic network composed of Integrate-and-Fire spiking neurons, focusing on its mean-field asymptotics. We consider an invariant probability measure of the McKean-Vlasov equation and establish an explicit sufficient condition to ensure the local stability of this invariant distribution. Furthermore, we prove a conjecture proposed initially by J. Touboul and P. Robert regarding the bistable nature of a specific instance of this neuronal model.
Cormier, Quentin
September 27, 2024
Read article
Informática y matemáticas aplicadas
TheoretiCS
TheoretiCS
Creada en 2021, TheoretiCS cubre todas las áreas de la informática teórica (Theoretical Computer Science, TCS). Esfuerzo conjunto de la comunidad TCS, la revista es publicada por la Fundación TheoretiCS, una organización sin ánimo de lucro situada en Alemania. La revista publica regularmente en inglés trabajos de investigación, incluyendo versiones revisadas y ampliadas de documentos de conferencias.
- Director de publicación: Thomas Schwentick
- Redactores en jefe: Anca Muscholl y Uri Zwick
- Tipo de soporte: electrónico
- Periodicidad: sobre la marcha
- Año de creación: 2021
- Fecha de publicación en Episciences: 2021
- eISSN: 2751-4838
- Disciplinas: informática teórica
- Idiomas de publicación: inglés
- Procedimiento de evaluación: evaluación simple ciega
- CC BY 4.0 licence
- Editor: TheoretiCS Foundation e.V.
- Dirección postal: c/o Thomas Schwentick – Schillingstr. 23, D-44139 Dortmund
- País: Alemania
- Contacto: theoretics AT episciences.org
Últimos artículos
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as in [Ben-Sasson and Wigderson '01] and highly unbalanced, dense graphs as in [Raz '04] and [Razborov '03, '04]. We obtain our results by revisiting Razborov's pseudo-width method for PHP formulas over dense graphs and extending it to sparse graphs. This further demonstrates the power of the pseudo-width method, and we believe it could potentially be useful for attacking also other longstanding open problems for resolution and other proof systems.
de Rezende, Susanna F.
March 25, 2025
Read article
Regular Languages in the Sliding Window Model
We study the space complexity of the following problem: For a fixed regular language $L$, we receive a stream of symbols and want to test membership of a sliding window of size $n$ in $L$. For deterministic streaming algorithms we prove a trichotomy theorem, namely that the (optimal) space complexity is either constant, logarithmic or linear, measured in the window size $n$. Additionally, we provide natural language-theoretic characterizations of the space classes. We then extend the results to randomized streaming algorithms and we show that in this setting, the space complexity of any regular language is either constant, doubly logarithmic, logarithmic or linear. Finally, we introduce sliding window testers, which can distinguish whether a sliding window of size $n$ belongs to the language $L$ or has Hamming distance $> \epsilon n$ to $L$. We prove that every regular language has a deterministic (resp., randomized) sliding window tester that requires only logarithmic (resp., constant) space.
Ganardi, Moses
March 06, 2025
Read article