Join us

Journals

Informatics and Applied Mathematics

ARIMA

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

ARIMA

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

The Revue africaine de recherche en informatique et mathématiques appliquées (ARIMA) was born in 2002 from a North/South scientific collaboration carried out in the wake of the activities of the African Colloquium for Research in Computer Science and Applied Mathematics (Colloque africain pour la recherche en informatique et mathématiques appliquées, CARI). The journal publishes the research results of these collaborations in French and English on an ongoing basis.

  • Director of publication: Maurice Tchuenté
  • Editor-in-chief: Nabil Gmati ; Mathieu Roche ; Tayou Djamegni Clémentin
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2002
  • Date of publication on Episciences: 2016
  • eISSN: 1638-5713
  • Subjects: Computer Science and Applied Mathematics
  • Languages of publication: English, French
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: African Society in Digital Science
    • Address: Department of Mathematics and Computer Science, Faculty of Science, University of Dschang, P.O. Box 96 Dschang
    • Country: Cameroon
  • Contact: arima AT episciences.org
See website

Latest articles

Synthèse multi-cible des systèmes de contrôle-commande à l'aide de l'approche IDM

Le GRAFCET est un puissant langage de modélisation graphique pour la spécification de contrôleurs dans des systèmes à événements discrets. Il prend en compte des structures hiérarchiques ainsi que des contraintes structurelles et sémantiques.Ici, nous proposons d'utiliser un modèle de spécification GRAFCET dans une approche d'ingénierie dirigée par les modèles (IDM) pour la synthèse multi-cible de systèmes de contrôle commande embarqués basés sur des microcontrôleurs.Dans cette approche, un métamodèle GRAFCET est associé à un métamodèle microcontrôleur, lequel caractérise les fonctionnalités de la plateforme spécifique microcontrôleur à considérer lors de la génération de code.Ce métamodèle GRAFCET proposé prend en compte la modélisation des expressions pour faciliter la vérification du modèle et une interprétation facile des événements GRAFCET ainsi que des contraintes de temps. Les règles de transformation utiles à la génération de code pour des microcontrôleurs C-programmables sont ensuite présentées.Comme application, nous présentons une plateforme basée sur Eclipse EMF, Object Constraint Language (OCL) et le moteur de génération de code Acceleo.
Nzebop Ndenoka, Gérard
April 09, 2025
Read article

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
Informatics and Applied Mathematics

Compositionality

Compositionality

Founded in 2017, Compositionality welcomes research articles in English in the field of the mathematics of composition across all disciplines. The journal is published by the Compositionality Charitable Incorporated Organisation.

  • Director of publication: John Baez
  • Editors-in-chief: Aleks Kissinger ; Joachim Kock
  • Medium: electronic
  • Frequency: annual
  • Date created: 2017
  • Date of publication on Episciences: 2024
  • eISSN: 2631-4444
  • Subjects: mathematics, computation, logic, physics, chemistry, engineering, linguistics, cognition
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Compositionality Charitable Incorporated Organisation
    • Address: 108 Kennington Road, Kennington, Oxford, OX1 5PE
    • Country: United Kingdom
  • Contact: compositionality AT episciences.org
See website

Latest articles

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
Informatics and Applied Mathematics

DMTCS

[Discrete Mathematics & Theoretical Computer Science]

DMTCS

Discrete Mathematics & Theoretical Computer Science

Discrete Mathematics & Theoretical Computer Science (DMTCS) is a peer-reviewed journal created in 1997. As a member of the DMTCS Association, it publishes research articles in English in the fields of discrete mathematics and theoretical computer science, especially at the intersection of these two disciplines.

  • Director of publication: Jens Gustedt
  • Editors-in-chief: Christoph Haase, Dieter Rautenbach, Sergi Elizalde and Hadas Shachnai
  • Medium: electronic
  • Frequency: continuous
  • Date created: 1997
  • Date of publication on Episciences: 2016
  • eISSN: 1365-8050
  • Subjects: mathematics, computer science
  • Languages of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Association DMTCS
    • Address: c/o Jens Gustedt, 67A avenue Jean-Jaurès, 67100 Strasbourg
    • Country: France
  • Contact: dmtcs AT episciences.org
See website

Latest articles

The complexity of recognizing $ABAB$-free hypergraphs

The study of geometric hypergraphs gave rise to the notion of $ABAB$-free hypergraphs. A hypergraph $\mathcal{H}$ is called $ABAB$-free if there is an ordering of its vertices such that there are no hyperedges $A,B$ and vertices $v_1,v_2,v_3,v_4$ in this order satisfying $v_1,v_3\in A\setminus B$ and $v_2,v_4\in B\setminus A$. In this paper, we prove that it is NP-complete to decide if a hypergraph is $ABAB$-free. We show a number of analogous results for hypergraphs with similar forbidden patterns, such as $ABABA$-free hypergraphs. As an application, we show that deciding whether a hypergraph is realizable as the incidence hypergraph of points and pseudodisks is also NP-complete.
Damásdi, Gábor
April 24, 2025
Read article

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
Informatics and Applied Mathematics
Proceedings

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—publishes proceedings of conferences and workshops in English that include significant theoretical advances in computer science and theoretical informatics.

  • Director of publication: Bruno Sportisse
  • Editor-in-chief: Michael Mislove
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2022
  • Date of publication on Episciences: 2023
  • eISSN: 2969-2431
  • Subjects: computer science, theoretical informatics
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Inria
    • Address: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • Country: France
  • Contact: entics AT episciences.org
See website

Latest articles

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
Informatics and Applied Mathematics

FI

[Fundamenta Informaticae]

FI

Fundamenta Informaticae

Fundamenta Informaticae, established in 1977, is a peer-reviewed scientific journal covering all areas of computer science, with main focus on theoretical foundations. The journal is published as Series IV of Annales Societatis Mathematicae Polonae, by the Polish Mathematical Society.

  • Director of publication: Prof. Jacek Miękisz
  • Editor-in-chief: Bartek Klin
  • Medium: print and electronic
  • Frequency: 3-4 volumes per year
  • Date created: 1977
  • Date of publication on Episciences: 2020
  • eISSN: 1875-8681
  • Subjects: computer science
  • Languages of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Polish Mathematical Society
    • Address: ul. Śniadeckich 8, 00-656 Warszawa
    • Country: Poland
  • Contact: fi AT episciences.org
See website

Latest articles

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
Informatics and Applied Mathematics
Social Sciences and Humanities

JDMDH

[Journal of Data Mining and Digital Humanities]

JDMDH

Journal of Data Mining and Digital Humanities

Created in 2014, the Journal of Data Mining and Digital Humanities (JDMDH) is situated at the intersection of data mining and digital humanities. The articles published concern both knowledge extraction and management (network analysis, information extraction, semantic web, preference analysis, machine learning) and the humanities and social sciences (historical, political, linguistic, sociological, geographical, communication and archiving) in the digital age.

  • Director of publication: Bruno Sportisse
  • Editors-in-chief: Richi Nayak ; Laurent Romary ; Nicolas Turenne
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2014
  • Date of publication on Episciences: 2014
  • eISSN: 2416-5999
  • Subjects: social sciences and humanities, digital humanities, text mining
  • Languages of publication: English, French
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Inria
    • Address: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • Country: France
  • Contact: jdmdh AT episciences.org
See website

Latest articles

Exploring Historical Labor Markets: Computational Approaches to Job Title Extraction

Historical job advertisements provide invaluable insights into the evolution of labor markets and societaldynamics. However, extracting structured information, such as job titles, from these OCRed and unstructuredtexts presents significant challenges. This study evaluates four distinct computational approachesfor job title extraction: a dictionary-based method, a rule-based approach leveraging linguistic patterns,a Named Entity Recognition (NER) model fine-tuned on historical data, and a text generation modeldesigned to rewrite advertisements into structured lists.Our analysis spans multiple versions of the ANNO dataset, including raw OCR, automatically postcorrected,and human-corrected text, as well as an external dataset of German historical job advertisements.Results demonstrate that the NER approach consistently outperforms other methods, showcasingrobustness to OCR errors and variability in text quality. The text generation approach performs well onhigh-quality data but exhibits greater sensitivity to OCR-induced noise. While the rule-based method isless effective overall, it performs relatively well for ambiguous entities. The dictionary-based approach,though limited in precision, remains stable across datasets.This study highlights the impact of text quality on extraction performance and underscores the need foradaptable, generalizable methods. Future work should focus on integrating hybrid approaches, expandingannotated datasets, and improving OCR correction techniques to enhance the extraction of structuredinformation from historical texts. These advancements will enable deeper exploration of labor markettrends and contribute to the broader field of digital humanities.
Adam, Raven
April 02, 2025
Read article

Evaluating ChatGPT-4 and Machine Learning Models for Sentiment Analysis on a Multi-Script Moroccan Arabic Corpus: Insights, Challenges, and Future Directions

The application of Large Language Models (LLMs) to low-resource languages and dialects, such as Moroccan Arabic (MA), remains a relatively unexplored area. This study evaluates the performance of ChatGPT-4, fine-tuned BERT models, FastText embeddings, and traditional machine learning approaches for sentiment analysis on MA. Using two publicly available MA datasets—the Moroccan Arabic Corpus (MAC) from X (formerly Twitter) and the Moroccan Arabic YouTube Corpus (MYC)—we assess the ability of these models to detect sentiment across different contexts. Although fine-tuned models performed well, ChatGPT-4 exhibited substantial potential for sentiment analysis, even in zero-shot scenarios. However, performance on MA was generally lower than on Modern Standard Arabic (MSA), attributed to factors such as regional variability, lack of standardization, and limited data availability. Future work should focus on expanding and standardizing MA datasets, as well as developing new methods like combining FastText and BERT embeddings with attention mechanisms to improve performance on this challenging dialect. 
Mohamed HANNANI
April 02, 2025
Read article
Informatics and Applied Mathematics

JIPS

[Journal d’Interaction Personne-Système]

JIPS

Journal d’Interaction Personne-Système

Created in 2008 by the Association francophone d’interaction humain-machine, the Journal d’Interaction Personne-Système (JIPS) succeeded the Revue d’Interaction Homme-Machine (RIHM), itself founded in 1997 and active until 2007 (then becoming the Revue des Interactions Humaines Médiatisées).

JIPS ceased publication in April 2022; published articles remain accessible on the journal’s website.

  • Director of publication: Sophie Dupuy-Chessa
  • Medium: electronic
  • Collection: 2010-2020
  • Date created: 2008
  • Date of publication on Episciences: 2014
  • eISSN: 2418-1838
  • Subjects: computer science, engineering, technology, cognitive science
  • Languages of publication: English, French
  • CC BY 4.0 licence
  • Publisher: Association Francophone d’Interaction Homme-Machine (AFIHM)
    • Address: 385 rue de la Bibliothèque, 38041 Grenoble Cedex
    • Country: France
  • Contact: presidence AT afihm.org
See website

Latest articles

Informatics and Applied Mathematics

JoDaKISS

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

JoDaKISS

Journal of Data- and Knowledge-integrated Simulation Science

Coming soon

Journal of Data- and Knowledge-integrated Simulation Science (JoDaKISS) is an international, multidisciplinary journal dedicated to supporting and advancing simulation science by publishing high-quality data and software for scientific computer simulations. It is published by the Stuttgart Center of Simulation Science (SC SimTech, University of Stuttgart, Germany).

  • Director of publication: Holger Steeb
  • Editorial Board: Bernd Flemisch, Dominik Göddeke, Jeroen Hanselman, Jan Heiland, Sibylle Hermann, Melanie Herschel, Timo Koch, Holger Steeb
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2024
  • eISSN: 2944-7666
  • Subjects: Simulation Science, Data-Rich Experiments, Direct Numerical Simulations
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Stuttgart Center of Simulation Science (SC SimTech)
    • Address: Pfaffenwaldring 5a, 70569 Stuttgart
    • Country: Germany
  • Contact: jodakiss AT episciences.org
See website
Informatics and Applied Mathematics

LMCS

[Logical Methods in Computer Science]

LMCS

Logical Methods in Computer Science

Logical Methods in Computer Science (LMCS) publishes research articles in English on theoretical and practical areas of computer science involving logical methods, taken in a broad sense. Established in 2014, the journal is edited by Logical Methods in Computer Science e.V., a non-profit organisation whose aim is to facilitate the dissemination of scientific results related to logic in computer science.

  • Director of publication: Lars Birkedal
  • Editor-in-chief: Stefan Milius
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2014
  • Date of publication on Episciences: 2015
  • eISSN: 1860-5974
  • Subjects: computer science, logical methods
  • Languages of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Logical Methods in Computer Science e.V.
    • Country: Germany
  • Contact: lmcs AT episciences.org
See website

Latest articles

Drawing with Distance

Drawing (a multiset of) coloured balls from an urn is one of the most basic models in discrete probability theory. Three modes of drawing are commonly distinguished: multinomial (draw-replace), hypergeometric (draw-delete), and Polya (draw-add). These drawing operations are represented as maps from urns to distributions over multisets of draws. The set of urns is a metric space via the Kantorovich distance. The set of distributions over draws is also a metric space, using Kantorovich-over-Kantorovich. It is shown that these three draw operations are all isometries, that is, they exactly preserve the Kantorovich distances. Further, drawing is studied in the limit, both for large urns and for large draws. First it is shown that, as the urn size increases, the Kantorovich distances go to zero between hypergeometric and multinomial draws, and also between P\'olya and multinomial draws. Second, it is shown that, as the drawsize increases, the Kantorovich distance goes to zero (in probability) between an urn and (normalised) multinomial draws from the urn. These results are known, but here, they are formulated in a novel metric manner as limits of Kantorovich distances. We call these two limit results the law of large urns and the law of large draws.
Jacobs, Bart
April 30, 2025
Read article

String Diagrams for Premonoidal Categories

Premonoidal categories are monoidal categories without the interchange law while effectful categories are premonoidal categories with a chosen monoidal subcategory of interchanging morphisms. In the same sense that string diagrams, pioneered by Joyal and Street, are an internal language for monoidal categories, we show that string diagrams with an added "runtime object", pioneered by Alan Jeffrey, are an internal language for effectful categories and can be used as string diagrams for effectful, premonoidal, and Freyd categories.
Román, Mario
April 29, 2025
Read article
Informatics and Applied Mathematics

MNA

[Mathematical Neuroscience and Applications]

MNA

Mathematical Neuroscience and Applications

Established in 2021, the journal Mathematical Neuroscience and Applications (MNA) focuses on mathematical modelling and analysis in all areas of neuroscience, i.e. the study of the nervous system and its dysfunctions. It is a continuation of the Journal of Mathematical Neuroscience (2011-2021), previously published by Springer. The journal welcomes articles in English.

  • Director of publication: Bruno Sportisse
  • Editor-in-chief: Olivier Faugeras
  • Medium: electronic
  • Frequency: annual
  • Date created: 2021
  • Date of publication on Episciences: 2021
  • eISSN: 2801-0159
  • Subjects: mathematics, neuroscience
  • Languages of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Inria
    • Address: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • Country: France
  • Contact: mna AT episciences.org
See website

Latest articles

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
Informatics and Applied Mathematics

TheoretiCS

TheoretiCS

Established in 2021, TheoretiCS covers all areas of Theoretical Computer Science (TCS). A joint effort of the TCS community, the journal is published by the TheoretiCS Foundation, a non-profit organisation based in Germany. The journal publishes research papers in English on an ongoing basis, including revised and extended versions of conference papers.

  • Director of publication: Thomas Schwentick
  • Editors-in-chief: Anca Muscholl and Uri Zwick
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2021
  • Date of publication on Episciences: 2021
  • eISSN: 2751-4838
  • Subjects: Theoretical Computer Science
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: TheoretiCS Foundation e.V.
    • Address: c/o Thomas Schwentick – Schillingstr. 23, D-44139 Dortmund
    • Country: Germany
  • Contact: theoretics AT episciences.org
See website

Latest articles

PANDA: Query Evaluation in Submodular Width

In recent years, several information-theoretic upper bounds have been introduced on the output size and evaluation cost of database join queries. These bounds vary in their power depending on both the type of statistics on input relations and the query plans that they support. This motivated the search for algorithms that can compute the output of a join query in times that are bounded by the corresponding information-theoretic bounds. In this paper, we describe PANDA, an algorithm that takes a Shannon-inequality that underlies the bound, and translates each proof step into an algorithmic step corresponding to some database operation. PANDA computes answers to a conjunctive query in time given by the the submodular width plus the output size of the query. The version in this paper represents a significant simplification of the original version [ANS, PODS'17].
Khamis, Mahmoud Abo
April 30, 2025
Read article

Ortho-Radial Drawing in Near-Linear Time

An orthogonal drawing is an embedding of a plane graph into a grid. In a seminal work of Tamassia (SIAM Journal on Computing 1987), a simple combinatorial characterization of angle assignments that can be realized as bend-free orthogonal drawings was established, thereby allowing an orthogonal drawing to be described combinatorially by listing the angles of all corners. The characterization reduces the need to consider certain geometric aspects, such as edge lengths and vertex coordinates, and simplifies the task of graph drawing algorithm design. Barth, Niedermann, Rutter, and Wolf (SoCG 2017) established an analogous combinatorial characterization for ortho-radial drawings, which are a generalization of orthogonal drawings to cylindrical grids. The proof of the characterization is existential and does not result in an efficient algorithm. Niedermann, Rutter, and Wolf (SoCG 2019) later addressed this issue by developing quadratic-time algorithms for both testing the realizability of a given angle assignment as an ortho-radial drawing without bends and constructing such a drawing. In this paper, we further improve the time complexity of these tasks to near-linear time. We establish a new characterization for ortho-radial drawings based on the concept of a good sequence. Using the new characterization, we design a simple greedy algorithm for constructing ortho-radial drawings.
Chang, Yi-Jun
April 08, 2025
Read article