Juntar-se

Revistas

Informática e matemática aplicada

ARIMA

[Revue africaine de recherche en informatique et mathématiques appliquées]

ARIMA

Revue africaine de recherche en informatique et mathématiques appliquées

A ARIMA nasceu em 2002 de uma colaboração científica Norte/Sul realizada na base das atividades do Colóquio africano para a investigação em informática e matemática aplicada (CARI). A revista publica gradualmente, em francês e em inglês, os resultados provenientes destas colaborações.

  • Diretor de publicação: Maurice Tchuenté
  • Redators responsáveis: Nabil Gmati, Mathieu Roche, Tayou Djamegni Clémentin
  • Tipo de suporte: digital
  • Periodicidade: gradual
  • Ano de criação: 2002
  • Data de disponibilização online na Episciences: 2016
  • eISSN: 1638-5713
  • Disciplinas: informática e matemática aplicada
  • Idiomas da publicação: inglês, francês
  • Processo de avaliação: estudo cego
  • CC BY 4.0 licence
  • Editor: African Society in Digital Science
    • Endereço postal: Department of Mathematics and Computer Science, Faculty of Science, University of Dschang, P.O. Box 96 Dschang
    • País: Camarões
  • Contacto: arima AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo
Informática e matemática aplicada

Compositionality

Compositionality

Fundada em 2017, a Compositionality acolhe artigos de investigação em inglês no domínio da matemática da composição em todas as disciplinas. A revista é publicada pela Compositionality Charitable Incorporated Organisation.

  • Diretor de publicação: John Baez
  • Editores-chefes: Aleks Kissinger ; Joachim Kock
  • Tipo de suporte: digital
  • Periodicidade: anual
  • Ano de criação: 2017
  • Data de disponibilização online na Episciences: 2024
  • eISSN: 2631-4444
  • Disciplinas: matemática, computação, lógica, física, química, engenharia, linguística, cognição
  • Idiomas da publicação: inglês
  • Processo de avaliação: estudo cego
  • Licença CC BY 4.0
  • Editor: Compositionality Charitable Incorporated Organisation
    • Endereço postal: 108 Kennington Road, Kennington, Oxford, OX1 5PE
    • País: Reino Unido
  • Contacto: compositionality AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo
Informática e matemática aplicada

DMTCS

[Discrete Mathematics & Theoretical Computer Science]

DMTCS

Discrete Mathematics & Theoretical Computer Science

A Discrete Mathematics & Theoretical Computer Science (DMTCS) é uma revista especializada criada em 1997. Apoiada pela associação DMTCS, publica gradualmente artigos de investigação em inglês, nas áreas da matemática discreta e da informática teórica, em especial no cruzamento destas duas disciplinas.

  • Diretor de publicação: Jens Gustedt
  • Redators e redatora responsáveis: Christoph Haase, Dieter Rautenbach, Sergi Elizalde e Hadas Shachnai
  • Tipo de suporte: digital
  • Periodicidade: gradual
  • Ano de criação
  • Data de disponibilização online na Episciences
  • eISSN: 1365-8050
  • Disciplinas: matemática, informática
  • Idiomas da publicação: inglês
  • Processo de avaliação: estudo cego
  • CC BY 4.0 licence
  • Editor: Association DMTCS
    • Endereço postal: c/o Jens Gustedt, 67A avenue Jean-Jaurès, 67100 Strasbourg
    • País: França
  • Contacto: dmtcs AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo
Actas de conferências
Informática e matemática aplicada

ENTICS

[Electronic Notes in Theoretical Informatics and Computer Science]

ENTICS

Electronic Notes in Theoretical Informatics and Computer Science

A ENTICS, Electronic Notes in Theoretical Informatics and Computer Science, criada em 2022, publica, gradualmente em inglês, atas de conferências e de workshops de informática teórica.

  • Diretor de publicação: Bruno Sportisse
  • Redator responsável: Michael Mislove
  • Tipo de suporte: digital
  • Periodicidade: gradual
  • Ano de criação: 2022
  • Data de disponibilização online na Episciences: 2023
  • eISSN: 2969-2431
  • Disciplinas: informática teórica
  • Idiomas da publicação: inglês
  • Processo de avaliação: estudo cego
  • Licence CC BY 4.0
  • Editor: Inria
    • Endereço postal: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • País: França
  • Contacto: entics AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo
Informática e matemática aplicada

FI

[Fundamenta Informaticae]

FI

Fundamenta Informaticae

Fundada em 1977, a Fundamenta Informaticae é uma revista científica especializada que abrange todas as áreas da informática, com um foco especial nos fundamentos teóricos. A revista é publicada na série IV das Annales Societatis Mathematicae Polonae, pela Sociedade matemática polaca.

  • Diretor de publicação: Prof. Jacek Miękisz
  • Redator responsável: Bartek Klin
  • Tipo de suporte: papel e digital
  • Periodicidade: 3 a 4 volumes por ano
  • Ano de criação: 1977
  • Data de disponibilização online na Episciences: 2020
  • eISSN: 1875-8681
  • Disciplinas: informática
  • Idiomas da publicação: inglês
  • Processo de avaliação: estudo cego
  • CC BY 4.0 licence
  • Editor: Polish Mathematical Society
    • Endereço postal: ul. Śniadeckich 8, 00-656 Warszawa
    • País: Polónia
  • Contacto: fi AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo
Ciências humanas e sociais
Informática e matemática aplicada

JDMDH

[Journal of Data Mining and Digital Humanities]

JDMDH

Journal of Data Mining and Digital Humanities

Criada em 2014, a Journal of Data Mining and Digital Humanities (JDMDH) situa-se na interseção da extração de dados e das humanidades digitais. Os artigos publicados, em inglês ou em francês, referem-se tanto à prospeção e à gestão dos conhecimentos (análise das redes, extração de informação, web semântica, análise das preferências, aprendizagem automática) como nas ciências humanas e sociais (históricas, políticas, linguísticas, sociológicas, geográficas, da comunicação e do arquivo) na era do digital.

  • Diretor de publicação: Bruno Sportisse
  • Redators responsáveis: Richi Nayak, Laurent Romary e Nicolas Turenne
  • Tipo de suporte: digital
  • Periodicidade: gradual
  • Ano de criação: 2014
  • Data de disponibilização online na Episciences: 2014
  • eISSN: 2416-5999
  • Disciplinas: humanidades digitais
  • Idiomas da publicação: inglês, francês
  • Processo de avaliação: estudo cego
  • CC BY 4.0 licence
  • Editor: Inria
    • Endereço postal: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • País: França
  • Contacto: jdmdh AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo
Informática e matemática aplicada

JIPS

[Journal d’Interaction Personne-Système]

JIPS

Journal d’Interaction Personne-Système

Criada em 2008 pela Association francophone d’interaction humain-machine, a Journal d’Interaction Personne-Système (JIPS) sucede a Revue d’Interaction Homme-Machine (RIHM) fundada em 1997 e ativa até 2007 (tornando-se de seguida a Revue des Interactions Humaines Médiatisées).

A JIPS deixou de publicar em abril de 2022; os artigos publicados permanecem no site da revista.

  • Diretora de publicação: Sophie Dupuy-Chessa
  • Tipo de suporte: digital
  • Estado da coleção: 2010-2020
  • Ano de criação: 2008
  • Data de disponibilização online na Episciences: 2014
  • eISSN: 2418-1838
  • Disciplinas: engenharia, tecnologias, ciências cognitivas
  • Idiomas da publicação: inglês, francês
  • CC BY 4.0 licence
  • Editor: Association Francophone d’Interaction Homme-Machine (AFIHM)
    • Endereço postal: 385 rue de la Bibliothèque, 38041 Grenoble Cedex
    • País: França
  • Contacto: presidence AT afihm.org
Ver o sítio web

Últimos artigos

Informática e matemática aplicada

JoDaKISS

[Journal of Data- and Knowledge-integrated Simulation Science]

JoDaKISS

Journal of Data- and Knowledge-integrated Simulation Science

Em breve

O Journal of Data- and Knowledge-integrated Simulation Science (JoDaKISS) é uma revista internacional e multidisciplinar dedicada a apoiar e a fazer avançar a ciência da simulação através da publicação de dados e software de alta qualidade para simulações científicas em computador. É publicada pelo Centro de Ciência da Simulação de Estugarda (SC SimTech, Universidade de Estugarda, Alemanha).

  • Diretor de publicação: Holger Steeb
  • Conselho Editorial: Bernd Flemisch, Dominik Göddeke, Jeroen Hanselman, Jan Heiland, Sibylle Hermann, Melanie Herschel, Timo Koch, Holger Steeb
  • Tipo de suporte: digital
  • Periodicidade: gradual
  • Ano de criação: 2024
  • Disciplinas: ciência da simulação, experiências ricas em dados, simulações numéricas diretas
  • Idiomas da publicação: inglês
  • Processo de avaliação: estudo cego
  • Licença CC BY 4.0
  • Editor: Stuttgart Center of Simulation Science (SC SimTech)
    • Endereço postal: Pfaffenwaldring 5a, 70569 Stuttgart
    • País: Alemanha
  • Contacto: jodakiss AT episciences.org
Ver o sítio web
Informática e matemática aplicada

LMCS

[Logical Methods in Computer Science]

LMCS

Logical Methods in Computer Science

A Logical Methods in Computer Science (LMCS) publica gradualmente artigos de investigação em inglês sobre áreas teóricas e práticas da informática envolvendo métodos lógicos, no sentido mais amplo. Criada em 2014, a revista é editada pela Logical Methods in Computer Science e.V., uma organização sem fins lucrativos cujo objetivo é facilitar a difusão dos resultados científicos relativos à lógica em informática.

  • Diretor de publicação: Lars Birkedal
  • Redator responsável: Stefan Milius
  • Tipo de suporte: digital
  • Periodicidade: gradual
  • Ano de criação: 2014
  • Data de disponibilização online na Episciences: 2015
  • eISSN: 1860-5974
  • Disciplinas: métodos lógicos
  • Idiomas da publicação: inglês
  • Processo de avaliação: estudo cego
  • CC BY 4.0 licence
  • Editor: Logical Methods in Computer Science e.V.
    • País: Alemanha
  • Contacto: lmcs AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo
Informática e matemática aplicada

MNA

[Mathematical Neuroscience and Applications]

MNA

Mathematical Neuroscience and Applications

Criada em 2021, a revista Mathematical Neuroscience and Applications (MNA) preocupa-se com a modelização e a análise matemática em todas as áreas das neurociências, isto é, o estudo do sistema nervoso e das suas disfunções. É a continuidade do Journal of Mathematical Neuroscience (2011-2021), anteriormente publicado na Springer. A revista acolha artigos na língua inglesa.

  • Diretor de publicação: Bruno Sportisse
  • Redator responsável: Olivier Faugeras
  • Tipo de suporte: digital
  • Periodicidade: anual
  • Ano de criação: 2021
  • Data de disponibilização online na Episciences: 2021
  • eISSN: 2801-0159
  • Disciplinas: neurociências
  • Idiomas da publicação: inglês
  • Processo de avaliação: estudo cego
  • CC BY 4.0 licence
  • Editor: Inria
    • Endereço postal: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • País: França
  • Contacto: mna AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo
Informática e matemática aplicada

TheoretiCS

TheoretiCS

Criada em 2021, a TheoretiCS abrange todas as áreas da informática teórica (Theoretical Computer Science, TCS). Resultado de um esforço conjunto da comunidade TCS, a revista é publicada pela Fundação TheoretiCS, uma organização sem fins lucrativos situada na Alemanha. A revista publica gradualmente trabalhos de investigação em inglês, incluindo versões revistas e extensões de artigos de conferências.

  • Diretor de publicação: Thomas Schwentick
  • Redators responsáveis: Anca Muscholl e Uri Zwick
  • Tipo de suporte: digital
  • Periodicidade: gradual
  • Ano de criação: 2021
  • Data de disponibilização online na Episciences: 2021
  • eISSN: 2751-4838
  • Disciplinas: informática teórica
  • Idiomas da publicação: inglês
  • Processo de avaliação: estudo cego
  • CC BY 4.0 licence
  • Editor: TheoretiCS Foundation e.V.
    • Endereço postal: c/o Thomas Schwentick – Schillingstr. 23, D-44139 Dortmund
    • País: Alemanha
  • Contacto: theoretics AT episciences.org
Ver o sítio web

Últimos artigos

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
Ler o artigo

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
Ler o artigo