Author name cluster

G. Pacini

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

I&C Journal 1996 Journal Article

Symbol–Relation Grammars: A Formalism for Graphical Languages

F. Ferrucci
G. Pacini
G. Satta
M.I. Sessa
G. Tortora
M. Tucci
G. Vitiello

A common approach to the formal description of pictorial and visual languages makes use of formal grammars and rewriting mechanisms. The present paper is concerned with the formalism of Symbol–Relation Grammars (SR grammars, for short). Each sentence in an SR language is composed of a set of symbol occurrences representing visual elementary objects, which are related through a set of binary relational items. The main feature of SR grammars is the uniform way they use context-free productions to rewrite symbol occurrences as well as relation items. The clearness and uniformity of the derivation process for SR grammars allow the extension of well-established techniques of syntactic and semantic analysis to the case of SR grammars. The paper provides an accurate analysis of the derivation mechanism and the expressive power of the SR formalism. This is necessary to fully exploit the capabilities of the model. The most meaningful features of SR grammars as well as their generative power are compared with those of well-known graph grammar families. In spite of their structural simplicity, variations of SR grammars have a generative power comparable with that of expressive classes of graph grammars, such as the edNCE and the N-edNCE classes.

Details DOI

I&C Journal 1995 Journal Article

Redundancy Elimination and Loop Checks for Logic Programs

F. Ferrucci
G. Pacini
M.I. Sessa

A simple analysis of the arguments developed by Bol et al. (Theoret. Comput. Sci. 86, 35-79 (1991)) shows that an actual reason for the nonexistence of a complete sound simple check for all function-free programs is the presence in the resolvents of potentially unlimited sequences of atoms chained by common variables. This hints that a limitation of the number of variables generating this kind of chain could guarantee the applicability of complete simple loop checks. This line is followed in the paper, and quite general classes of logic programs are characterized, without any direct imposition on the structures of the rules. This objective is accomplished by exploiting a variant of SLD-resolution, which is able to perform a systematic elimination of redundant atoms from resolvents. As a notable result, it turns out that the equality loop check is complete for our class of logic programs. This seems to suggest that the necessity of using subsumption loop checks instead of equality checks is essentially due to the presence of redundant atoms in resolvents.

Details DOI

TCS Journal 1993 Journal Article

Legality concepts for three-valued logic programs

G. Nota
S. Orefice
G. Pacini
F. Ruggiero
G. Tortora

In several application fields, sentences can assume, besides the usual values true and false, a third value that signals their unacceptability. This may happen when a query to a database violates the database constraints or in typed logic programming, where a goal which does not satisfy the type constraints can be considered unacceptable. Here a three-valued Horn logic is presented, where the third value has the meaning of “illegal”, i. e. unacceptable. The extension of the conventional logic operators is considered, and a model-theoretic semantics for three-valued Horn programs is provided, which allows a formal definition of legality (i. e. acceptability) of logic formulas and programs. For the class of legal three-valued logic programs the use of the traditional SLD resolution algorithm is proven to be sound. Finally, it is shown that the legality check of a three-valued logic program can be also carried out through SLD resolution.

Details DOI

TCS Journal 1981 Journal Article

About the implementability and the power of equationally defined data abstractions

G. Callegarin
G. Pacini

The question of implementability and expressive power of equational axiom definitions of data abstractions is faced in the paper from the point of view of computability theory. A definition of implementable algebra is given, which looks reasonable and very general. With respect to the given definition it is proved that, if the least congruence semantics is accepted, an equationally defined data algebra is implementable if and only if the least congruence on terms induced by the equational definition is decidable. Moreover, the paper shows that there are: (a) equationally defined data algebras that cannot be implemented; (b) implementable algebras that cannot be expressed in any way by equational axioms.

Details DOI