Wyniki wyszukiwania - BazTech

1

A Many-sorted Polyadic Modal Logic

Leuştean Ioana, Moangă Natalia, Şerbănuţă Traian Florin

Fundamenta Informaticae

|

2020

|

Vol. 173, nr 2-3

191--215

EN

We propose a general system that combines the powerful features of modal logic and many-sorted reasoning. Its algebraic semantics leads to a many-sorted generalization of boolean algebras with operators, for which we prove the analogue of the Jónsson-Tarski theorem. Our goal was to deepen the connections between modal logic and program verification, while also testing the expressiveness of our system by defining a small imperative language and its operational semantics.

2

On the directly and subdirectly irreducible many-sorted algebras

Climent-Vidal J., Soliveres-Tur J.

Demonstratio Mathematica

|

2015

|

Vol. 48, nr 1

1--12

EN

A theorem of single-sorted universal algebra asserts that every finite algebra can be represented as a product of a finite family of finite directly irreducible algebras. In this article, we show that the many-sorted counterpart of the above theorem is also true, but under the condition of requiring, in the definition of directly reducible many-sorted algebra, that the supports of the factors should be included in the support of the many-sorted algebra. Moreover, we show that the theorem of Birkhoff, according to which every single-sorted algebra is isomorphic to a subdirect product of subdirectly irreducible algebras, is also true in the field of many-sorted algebras.

3

Subdirectly irreducible fibered automata, Part 2

Mućka A.

Demonstratio Mathematica

|

2011

|

Vol. 44, nr 1

1-15

EN

An earlier paper characterized all subdirectly irreducible permutational fibered automata. This paper characterizes all subdirectly irreducible fibered automata which are not permutational. The characterization is both graphtheoretical and algebraic.

4

Subdirectly irreducible fibered automata

Mućka A.

Demonstratio Mathematica

|

2010

|

Vol. 43, nr 4

739-753

EN

A permutational automaton is a fibered automaton with one-element event set or an empty state space. This paper characterizes all subdirectly irreducible permutational automata.

5

Nd-hypersubstitutions of many-sorted algebras

Denecke K., Lekkoksung S.

Demonstratio Mathematica

|

2010

|

Vol. 43, nr 3

519-537

EN

A non-deterministic hypersubstitution maps any operation symbol of type ? to a tree language. Non-deterministic hypersubstitutions can be extended to mappings which map tree languages to tree languages preserving the arities ([2]). We can extend those hypersubstitutions to many-sorted non-deterministic hypersubstitutions which map any operation symbol to a tree language of the corresponding sort ([5]). The aim of this paper is to show that the extension of a many-sorted non-deterministic hyper-substitution is an endomorphism of some clone and that the set of all non-deterministic hypersubstitutions of each sort forms a semigroup. These results can be applied to study M-solid many-sorted varieties of tree languages (see [4]).

6

First and Second Order Recursion on Abstract Data Types

Xu J., Zucker J.

Fundamenta Informaticae

|

2005

|

Vol. 67, nr 4

377--419

EN

This paper compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system of ``abstract computational procedures" based on a least fixed point operator, and Tucker and Zucker's system based on primitive recursion on the naturals together with a least number operator. We prove a conjecture of Feferman that (assuming A contains sorts for natural numbers and arrays of data) the two systems are equivalent. The main step in the proof is showing the equivalence of both systems to a system of computation by an imperative programming language with recursive calls. The result provides a confirmation for a Generalized Church-Turing Thesis for computation on abstract data types.