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: Cojocaru, Liliana | Mรคkinen, Erkki
Article Type: Research Article
Abstract: The regulated rewriting mechanism is one of the most efficient methods to augment the Chomsky hierarchy with a large variety of language classes. In this paper we investigate the derivation mechanism in regulated rewriting grammars such as matrix grammars, by studying their Szilard languages. We focus on the complexity of Szilard languages associated with unrestricted and leftmost-like derivations in matrix grammars, with or without appearance checking. The reason is twofold. First, to relate these classes of languages to parallel complexity classes such as ๐ฉ๐1 and ๐๐1 , and, second, to improve some previous results. We prove that unrestricted Szilard …languages and certain leftmost Szilard languages of context-free matrix grammars, without appearance checking, can be accepted by indexing alternating Turing machines in logarithmic time and space. Consequently, these classes are included in UE* -uniform ๐ฉ๐1 . Unrestricted Szilard languages of matrix grammars with appearance checking can be accepted by deterministic Turing machines in ๐ช(n log n) time and ๐ช(log n) space. Leftmost-like Szilard languages of context-free matrix grammars, with appearance checking, can be recognized by nondeterministic Turing machines by using the same time and space resources. Hence, all these classes are included in ๐๐1 . Show more
Keywords: matrix grammars, Szilard languages, (alternating) Turing machines, ๐ฉ๐^{1} and ๐๐^{1} complexity classes
DOI: 10.3233/FI-2013-817
Citation: Fundamenta Informaticae, vol. 123, no. 4, pp. 381-399, 2013
Authors: Jiang, Feng | Wan, Xiaoyan | Sui, Yuefei | Cao, Cungen | Du, Junwei
Article Type: Research Article
Abstract: The traditional relational database model (RDM) is not effective for dealing with imprecise and uncertain data as it deals with precise and unambiguous data. Hence, Beaubouef et al. proposed the rough relational database model (RRDM) for the management of uncertainty in relational databases. Beaubouef et al. defined the corresponding rough relational operators in rough relational databases as in ordinary relational databases. And to give an effective measure of uncertainty in rough relational databases, they defined the rough relation entropy. In this paper, we further discuss the issues of relational operations and uncertainty measure in rough relational databases. We give some …new definitions for rough relational operators and rough relation entropy in rough relational databases. Furthermore, we discuss the basic properties of rough relational operators and rough relation entropy, as well as the connections between rough relational operators and rough relation entropy. Show more
Keywords: Rough sets, RDM, RRDM, rough relation entropy, relational operations
DOI: 10.3233/FI-2013-818
Citation: Fundamenta Informaticae, vol. 123, no. 4, pp. 401-416, 2013
Authors: Schmitt, Dominique | Spehner, Jean-Claude
Article Type: Research Article
Abstract: Araucarias have been introduced by Schott and Spehner as trees which appear in the minimal automaton of the shuffle of words. We give here a new definition of araucarias which is more constructive and we prove that our definition of araucarias is equivalent to the original one. From the new definition we derive an optimal algorithm for the construction of araucarias and a new method for calculating their size. Moreover we characterize araucarias by properties of their maximal paths, by associating a capacity to every edge. We then show that every araucaria can be obtained by grafting and merging smaller …araucarias. We prove also that every directed tree can be embedded in an araucaria. Moreover we define a capacity for every vertex of an araucaria, which leads to different new enumeration formulas for araucarias. Show more
Keywords: Algorithms, trees, symmetric polynomials, combinatorics, shuffle of words
DOI: 10.3233/FI-2013-819
Citation: Fundamenta Informaticae, vol. 123, no. 4, pp. 417-445, 2013
Authors: Simson, Daniel
Article Type: Research Article
Abstract: By computer algebra technique and computer computations, we solve the mesh morsification problems 1.10 and present a classification of irreducible mesh roots systems, for some of the simply-laced Dynkin diagrams $\rmDelta \in \{\mathbb{A}_n,\mathbb{D}_n, \mathbb{E}_6, \mathbb{E}_7, \mathbb{E}_8\}$. The methods we use show an importance of computer algebra tools in solving difficult modern algebra problems of enough high complexity that had no solution by means of standard theoretical tools only. Inspired by results of Sato [Linear Algebra Appl. 406(2005), 99-108] and a mesh quiver description of indecomposable representations of finite-dimensional algebras and their derived categories explained in [London Math. Soc. Lecture Notes …Series, Vol. 119, 1988] and [Fund. Inform. 109(2011), 425-462] (see also 5.11), given a Dynkin diagram ฮ, with n vertices and the Euler quadratic form q$_\rmDelta : \mathbb{Z}^n \rightarrow \mathbb{Z}$, we study the set Mor$_\rmDelta \subseteq \mathbb{M}_{n} (\mathbb{Z})$ of all morsifications of q$_\rmDelta$ [37], i.e., the non-singular matrices A $in \mathbb{M}_{n}(\mathbb{Z})$ such that its Coxeter matrix Cox$_A$ := -A · A$^{-tr}$ lies in Gl(n, \mathbb{Z}) and q$_{\rmDelta}$ (v) = v · A · v$^{tr}$, for all v $\in \mathbb{Z}n$. The matrix Weyl group \mathbb{W}$_\rmDelta$ (2.13) acts on Mor$_\rmDelta$ and the determinant detA $\in$ \mathbb{Z}, the order cA $\ge2$ of CoxA (i.e. the Coxeter number), and the Coxeter polynomial cox$_A$ (t) := det(t ·E-Cox$_A$) $\in$ \mathbb{Z}[t] are $\mathbb{W}_\rmDelta$-invariant. Moreover, the finite set $R_{q\rmDelta} = \{v \in \mthbb{Z}^n; q_\rmDelta (v) = 1\}$ of roots of q$_\rmDelta$ is Cox$_A$- invariant. The following problems are studied in the paper: (a) determine the $\mathbb{W}_\rmDelta$-orbits \cal{Orb}(A) of Mor$_\rmDelta$ and the set $\cal{CPol}_\rmDelta = \{cox_{A}(t); A \in Mor_\rmDelta\}$, (b) construct a finite minimal Cox$_A$-mesh quiver in $\mathbb{Z}^n$ containing all Cox$_A$-orbits of the finite set $R_{q\rmDelta}$ of roots of q$_\rmDelta$;. We prove that \cal{CPol}$_\rmDelta$ is a finite set and we construct algorithms allowing us to solve the problems for the morsifications $A = [a_{ij}] \in Mor_\rmDelta$, with $|a_{ij}| \le 2$. In this case, by computer algebra technique and computer computations, we prove that, for $n \le 8$, the number of the $\mathbb{W}_\rmDelta$-orbits \cal{Orb}(A) is at most 6, $s_\rmDelta := |\cal{CPol}_\rmDelta| \le 9$ and, given A,A' $\in$ Mor$_\rmDelta$ and $n \le 7$, the following three conditions are equivalent: (i) A' = $B^{tr}$ · A · B, for some B $\in$ Gl(n, \mathbb{Z}), (ii) cox$_{A}$(t) = cox$_{A'}$ (t), and (iii) cA · det A = c$_{A'}$ · det A'. We also show that s$_{\rmDelta}$ equals 6, 5, and 9, if $\rmDelta$ is the diagram $\mathbb{E}_6$, $\mathbb{E}_7$, and $\mathbb{E}_8$, respectively. Show more
Keywords: positive unit form, morsification, Dynkin diagram, Coxeter polynomial, Coxeter matrix, Coxeter spectrum, Euler bilinear form, Weyl group, mesh quiver of roots, mesh geometry
DOI: 10.3233/FI-2013-820
Citation: Fundamenta Informaticae, vol. 123, no. 4, pp. 447-490, 2013
Article Type: Other
Citation: Fundamenta Informaticae, vol. 123, no. 4, pp. 491-492, 2013
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]