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 192, issue 2

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.

Preface

Authors: Proietti, Maurizio | Villanueva, Alicia

Article Type: Editorial

DOI: 10.3233/FI-242190

Citation: Fundamenta Informaticae, vol. 192, no. 2, pp. i-ii, 2024

Get PDF

On Complexity Bounds and Confluence of Parallel Term Rewriting *

Authors: Baudon, Thaïs | Fuhs, Carsten | Gonnord, Laure

Article Type: Research Article

Abstract: 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 … Show more

Keywords: Term rewriting, confluence, complexity analysis, parallelism, static analysis

DOI: 10.3233/FI-242191

Citation: Fundamenta Informaticae, vol. 192, no. 2, pp. 121-166, 2024

Price: EUR 27.50

Proving Confluence in the Confluence Framework with CONFident

Authors: Gutiérrez, Raúl | Lucas, Salvador | Vítores, Miguel

Article Type: Research Article

Abstract: 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 … Show more

Keywords: confluence, program analysis, rewriting

DOI: 10.3233/FI-242192

Citation: Fundamenta Informaticae, vol. 192, no. 2, pp. 167-217, 2024

Price: EUR 27.50
Show more