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 188, issue 3

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.

Cost Automata, Safe Schemes, and Downward Closures

Authors: Barozzini, David | Clemente, Lorenzo | Colcombet, Thomas | Parys, Paweł

Article Type: Research Article

Abstract: In this work we prove decidability of the model-checking problem for safe recursion schemes against properties defined by alternating B-automata. We then exploit this result to show how to compute downward closures of languages of finite trees recognized by safe recursion schemes. Higher-order recursion schemes are an expressive formalism used to define languages of finite and infinite ranked trees by means of fixed points of lambda terms. They extend regular and context-free grammars, and are equivalent in expressive power to the simply typed λY -calculus and collapsible pushdown automata. Safety in a syntactic restriction which limits their expressive power. … Show more

Keywords: Cost logics, cost automata, downward closures, higher-order recursion schemes, safe recursion schemes

DOI: 10.3233/FI-222145

Citation: Fundamenta Informaticae, vol. 188, no. 3, pp. 127-178, 2022

Price: EUR 27.50

Structural Liveness of Immediate Observation Petri Nets

Authors: Jančar, Petr | Valůšek, Jiří

Article Type: Research Article

Abstract: We look in detail at the structural liveness problem (SLP) for subclasses of Petri nets, namely immediate observation nets (IO nets) and their generalized variant called branching immediate multi-observation nets (BIMO nets), that were recently introduced by Esparza, Raskin, and Weil-Kennedy. We show that SLP is PSPACE-hard for IO nets and in PSPACE for BIMO nets. In particular, we discuss the (small) bounds on the token numbers in net places that are decisive for a marking to be (non)live.

Keywords: Petri nets, immediate observation nets, structural liveness, complexity

DOI: 10.3233/FI-222146

Citation: Fundamenta Informaticae, vol. 188, no. 3, pp. 179-215, 2022

Price: EUR 27.50
Show more