You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Fundamenta Informaticae - Volume 184, issue 1

Purchase individual online access for 1 year to this journal.

Price: EUR 410.00
ISSN 0169-2968 (P)
ISSN 1875-8681 (E)

Impact Factor 2024: 0.4

Fundamenta Informaticae is an international journal publishing original research results in all areas of theoretical computer science. Papers are encouraged contributing:


- solutions by mathematical methods of problems emerging in computer science
- solutions of mathematical problems inspired by computer science.

Topics of interest include (but are not restricted to): theory of computing, complexity theory, algorithms and data structures, computational aspects of combinatorics and graph theory, programming language theory, theoretical aspects of programming languages, computer-aided verification, computer science logic, database theory, logic programming, automated deduction, formal languages and automata theory, concurrency and distributed computing, cryptography and security, theoretical issues in artificial intelligence, machine learning, pattern recognition, algorithmic game theory, bioinformatics and computational biology, quantum computing, probabilistic methods, & algebraic and categorical methods.

A Congruence-Based Perspective on Finite Tree Automata

Authors: Ganty, Pierre | Gutiérrez, Elena | Valero, Pedro

Article Type: Research Article

Abstract: We provide new insights on the determinization and minimization of tree automata using congruences on trees. From this perspective, we study a Brzozowski’s style minimization algorithm for tree automata. First, we prove correct this method relying on the following fact: when the automata-based and the language-based congruences coincide, determinizing the automaton yields the minimal one. Such automata-based congruences, in the case of word automata, are defined using pre and post operators. Now we extend these operators to tree automata, a task that is particularly challenging due to the reduced expressive power of deterministic top-down (or equivalently co-deterministic bottom-up) automata. We … Show more

DOI: 10.3233/FI-2021-2091

Citation: Fundamenta Informaticae, vol. 184, no. 1, pp. 1-47, 2021

Price: EUR 27.50

A Graph Theoretical Framework for the Strong Gram Classification of Non-negative Unit Forms of Dynkin Type 𝔸 n

Authors: Jiménez González, Jesús Arturo

Article Type: Research Article

Abstract: In the context of signed line graphs, this article introduces a modified inflation technique to study strong Gram congruence of non-negative (integral quadratic) unit forms, and uses it to show that weak and strong Gram congruence coincide among positive unit forms of Dynkin type 𝔸n . The concept of inverse of a quiver is also introduced, and is used to obtain and analyze the Coxeter matrix of non-negative unit forms of Dynkin type 𝔸n . With these tools, connected principal unit forms of Dynkin type 𝔸n are also classified up to strong congruence.

Keywords: Integral quadratic form, Gram congruence, quiver, Dynkin type, Coxeter matrix, edge-bipartite graph, signed line graph, 2020 MSC: 15A63, 15A21, 15B36, 05C22, 05C50, 05C76, 05B20

DOI: 10.3233/FI-2021-2092

Citation: Fundamenta Informaticae, vol. 184, no. 1, pp. 49-82, 2021

Price: EUR 27.50
Show more