Scientific Annals of Computer Science
"Alexandru Ioan Cuza" University of Iaşi
Volume XIV, 2004
Co-determinism and unambiguity of automata accepting finite or infinite words.,
pages 1-11
Stefan ANDREI, Wei-Ngan CHIN, Gheorghe GRIGORAS
Abstract |
BibTeX
Automata theory plays an important role in the verification
of finite-state systems. The deterministic automata are the
most prefered ones since the inclusion problem is decidable.
Similar to deterministic automata, it is worthwhile to
consider two other important classes for finite and infinite words,
such as: co-deterministic
automata and unambiguous automata. This paper describes related
subclasses of these automata, by comparison with existing terminology.
Hardly perfect graphs.,
pages 12-22
Cornelius CROITORU, Cristian FRASINARU, Elefterie OLARU, Mihai TALMACIU
Abstract |
BibTeX
We call a graph $G$ {it hardly perfect} if
for each its induced subgraph $G'$ there is an optimal coloring of $G$
assigning to the vertices of $G'$ a number of colors equal to the maximum
cardinality of a clique in $G'$ which can be extended to a maximum clique of $G$.
In this paper the combinatorial structure of hardly perfect graphs is completely described.
Using the characterization theorem and the fact that hardly perfect graphs are $P4$-free,
we were able to design a recognition algorithm with linear time complexity.
A Question Answering System for Italian Language.,
pages 23-35
Francesca BERTAGNA, Luminita CHIRAN
Abstract |
BibTeX
This paper introduces the general architecture of a prototype for monolingual
Italian Question Answering System (QA). The adopted strategies, the tools and
resources for the linguistic processing are presented, together with the system results.
The Quick Check Pre-unification Filter for Typed Grammars: Further Advances.,
pages 36-50
Liviu CIORTUZ
Abstract |
BibTeX
We present several significant improvements in the implementation of the
quick check pre-unification filter~cite{Ciortuz-2002a}~cite{Ciortuz-2002f},
and the potential way in which the design of the quick check~cite{KKCM-99}~cite{MCC-00}
can be further extended. We analyse the effect of these extensions on LinGO,
the large-scale HPSG grammar for Englishcite{LinGO-99}. Althought these developments
were done for the compiler system light~cite{Ciortuz-2002b}, most of them are
transferrable to non-compilation based systems.
On Hidden Algebra Semantics of Object Oriented Languages.,
pages 51-68
Gheorghe GRIGORAS, Dorel LUCANU
Abstract |
BibTeX
The paper presents a hidden algebra framework for specifying object-oriented
concepts like object identity, concurrent objects,
encapsulation, inheritance, polymorphism.
Iterative Algorithm for Construction of a Tree from its Pre-order and Post-order Traversals in Linear Time and Space.,
pages 69-80
Adrian DEACONU
Abstract |
BibTeX
A linear time and space iterative algorithm for construction of a tree from
its pre-order and post-order traversals is presented.
In the end the binary tree case is studied. In this case the solution is not unique.
The number of solutions is calculated and it is shown that all the solutions can
be found starting from a pre-determined one.
Multi-Valued Stable Semantics for Logic Programs.,
pages 81-90
Victor FELEA
Abstract |
BibTeX
We consider a set of $n+1$-truth values and a set of constant propositions one for
each truth value.
For a general logic program in sense Gelder, which may contain constant propositions,
$n+2$-valued interpretations and models are defined. For a program $P$, an operator
$psi_{n+2}$ is defined. This operator generalizes the operator
$psi$ defined by Przymusinski. Using the operator $psi_{n+2}$, a stable semantics
for the case multi-valued is introduced. For the case n=1 the three-valued stable
semantics introduced by Przymusinski is obtained.
Modelling and Verification with Jumping Petri Nets.,
pages 91-99
Cristian VIDRASCU
Abstract |
BibTeX
This paper presents a CREW (i.e., concurrent read exclusive write)
processes system, modelled by a jumping Petri net,
and proves some properties of the system.
