Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Purchase individual online access for 1 year to this journal.
Price: EUR 410.00Impact 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.
Authors: Engels, Gregor | Orejas, Fernando | Parisi-Presicce, Francesco
Article Type: Other
Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. i-ii, 2006
Authors: Ehrig, Hartmut | Padberg, Julia | Prange, Ulrike | Habel, Annegret
Article Type: Research Article
Abstract: Adhesive high-level replacement (HLR) systems are introduced as a new categorical framework for graph transformation in the double pushout (DPO) approach, which combines the well-known concept of HLR systems with the new concept of adhesive categories introduced by Lack and Sobocinacute;ski. In this paper we show that most of the HLR properties, which had been introduced to generalize some basic results from the category of graphs to high-level structures, are valid already in adhesive HLR categories. This leads …to a smooth categorical theory of HLR systems which can be applied to a large variety of graphs and other visual models. As a main new result in a categorical framework we show the Critical Pair Lemma for the local confluence of transformations. Moreover we present a new version of embeddings and extensions for transformations in our framework of adhesive HLR systems. Show more
Keywords: high-level replacement systems, adhesive categories, adhesive HLR categories, graph transformation, local confluence of transformations, Critical Pair Lemma
Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 1-29, 2006
Authors: Ehrig, Hartmut | Ehrig, Karsten | Prange, Ulrike | Taentzer, Gabriele
Article Type: Research Article
Abstract: The concept of typed attributed graphs and graph transformation is most significant for modeling and meta modeling in software engineering and visual languages, but up to now there is no adequate theory for this important branch of graph transformation. In this article we give a new formalization of typed attributed graphs, which allows node and edge attribution. The first main result shows that the corresponding category is isomorphic to the category of algebras over a specific …kind of attributed graph structure signature. This allows to prove the second main result showing that the category of typed attributed graphs is an instance of "adhesive HLR categories". This new concept combines adhesive categories introduced by Lack and Sobociński with the well-known approach of high-level replacement (HLR) systems using a new simplified version of HLR conditions. As a consequence we obtain a rigorous approach to typed attributed graph transformation providing as fundamental results the Local Church-Rosser, Parallelism, Concurrency, Embedding and Extension Theorem and a Local Confluence Theorem known as Critical Pair Lemma in the literature. Show more
Keywords: typed attributed graph transformation, adhesive HLR categories, local confluence of transformations, Critical Pair Lemma
Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 31-61, 2006
Authors: Heckel, Reiko | Lajios, Georgios | Menge, Sebastian
Article Type: Research Article
Abstract: In distributed and mobile systems with volatile bandwidth and fragile connectivity, non-functional aspects like performance and reliability become more and more important. To formalize, measure, and predict such properties, stochastic methods are required. At the same time such systems are characterized by a high degree of architectural reconfiguration. Viewing the architecture of a distributed system as a graph, this is naturally modeled by graph transformations. To combine these two views, in this paper we …introduce stochastic graph transformation systems associating with each rule its application rate – the rate of the exponential distribution governing the delay of its application. Beside the basic definitions and a motivating example, we derive continuous time Markov chains, establish a link with continuous stochastic logic, deal with the problem of abstraction through graph isomorphisms, and discuss the analysis of properties by means of an experimental tool chain. Show more
Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 63-84, 2006
Authors: Chalopin, Jérémie | Métivier, Yves | Zielonka, Wiesław
Article Type: Research Article
Abstract: We examine the power and limitations of the weakest vertex relabelling system which allows to change a label of a vertex in function of its own label and of the label of one of its neighbours. We characterize the graphs for which two important distributed algorithmic problems are solvable in this model: naming and election.
Keywords: Distributed Computing, Local Computations, Election, Naming, Submersion
Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 85-114, 2006
Authors: Ehrenfeucht, Andrzej | Hage, Jurriaan | Harju, Tero | Rozenberg, Grzegorz
Article Type: Research Article
Abstract: In the context of graph transformation we look at the operation of switching, which can be viewed as a method for realizing global transformations of (group-labelled) graphs through local transformations of the vertices. In case vertices are given an identity, various relatively efficient algorithms exist for deciding whether a graph can be switched so that it contains some other graph, the query graph, as an induced subgraph. However, when considering graphs up to isomorphism, we immediately run into …the graph isomorphism problem for which no efficient solution is known. Surprisingly enough however, in some cases the decision process can be simplified by transforming the query graph into a "smaller" graph without changing the answer. The main lesson learned is that the size of the query graph is not the dominating factor, but its cycle rank. Although a number of our results hold specifically for undirected, unlabelled graphs, we propose a more general framework and give many positive and negative results for more general cases, where the graphs are labelled with elements of a (finitely generated abelian) group. Show more
Keywords: Seidel switching, graph algorithms, complexity, NP-completeness, embedding problem, cyclomatic number
Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 115-134, 2006
Authors: Ehrig, Hartmut | Ehrig, Karsten | Habel, Annegret | Pennemann, Karl-Heinz
Article Type: Research Article
Abstract: Graph constraints and application conditions are most important for graph grammars and transformation systems in a large variety of application areas. Although different approaches have been presented in the literature already there is no adequate theory up to now which can be applied to different kinds of graphs and high-level structures. In this paper, we introduce a general notion of graph constraints and application conditions and show under what conditions the basic results can be extended …from graph transformation to high-level replacement systems. In fact, we use the new framework of adhesive HLR categories recently introduced as combination of HLR systems and adhesive categories. Our main results are the transformation of graph constraints into right application conditions and the transformation from right to left application conditions in this new framework. The transformations are illustrated by a railroad control system with rail net constraints and application conditions. Show more
Keywords: graph transformation, constraints, application conditions, graphs, high-level structures, adhesive HLR categories
Citation: Fundamenta Informaticae, vol. 74, no. 1, pp. 135-166, 2006
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]