Page 1 Next

Displaying 1 – 20 of 28

Showing per page

A classification of rational languages by semilattice-ordered monoids

Archivum Mathematicum

We prove here an Eilenberg type theorem: the so-called conjunctive varieties of rational languages correspond to the pseudovarieties of finite semilattice-ordered monoids. Taking complements of members of a conjunctive variety of languages we get a so-called disjunctive variety. We present here a non-trivial example of such a variety together with an equational characterization of the corresponding pseudovariety.

A deductive calculus for conditional equational systems with built-in predicates as premises.

Revista Colombiana de Matemáticas

A semantic construction of two-ary integers

Discussiones Mathematicae - General Algebra and Applications

To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This...

Algebraic and graph-theoretic properties of infinite $n$-posets

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A $\Sigma$-labeled $n$-poset is an (at most) countable set, labeled in the set $\Sigma$, equipped with $n$ partial orders. The collection of all $\Sigma$-labeled $n$-posets is naturally equipped with $n$ binary product operations and $n$$\omega$-ary product operations. Moreover, the $\omega$-ary product operations give rise to $n$$...$

Algebraic and graph-theoretic properties of infinite n-posets

RAIRO - Theoretical Informatics and Applications

A Σ-labeled n-poset is an (at most) countable set, labeled in the set Σ, equipped with n partial orders. The collection of all Σ-labeled n-posets is naturally equipped with n binary product operations and nω-ary product operations. Moreover, the ω-ary product operations give rise to nω-power operations. We show that those Σ-labeled n-posets that can be generated from the singletons by the binary and ω-ary product operations form the free algebra on Σ in a variety axiomatizable by an infinite collection...

Axiomatizing omega and omega-op powers of words

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

In 1978, Courcelle asked for a complete set of axioms and rules for the equational theory of (discrete regular) words equipped with the operations of product, omega power and omega-op power. In this paper we find a simple set of equations and prove they are complete. Moreover, we show that the equational theory is decidable in polynomial time.

Axiomatizing omega and omega-op powers of words

RAIRO - Theoretical Informatics and Applications

In 1978, Courcelle asked for a complete set of axioms and rules for the equational theory of (discrete regular) words equipped with the operations of product, omega power and omega-op power. In this paper we find a simple set of equations and prove they are complete. Moreover, we show that the equational theory is decidable in polynomial time.

Composition-representative subsets.

Theory and Applications of Categories [electronic only]

Computability potential scales of $n$-element algebras with restrictions on arity.

Sibirskij Matematicheskij Zhurnal

Free Term Algebras

Formalized Mathematics

We interoduce a new characterization of algebras of normal forms of term rewriting systems [35] as algerbras of term free in itself (any function from free generators into the algebra generates endomorphism of the algebra). Introduced algebras are free in classes of algebras satisfying some sets of equalities. Their universes are subsets of all terms and the denotations of operation symbols are partially identical with the operations of construction of terms. These algebras are compiler algebras...

Introduction to coalgebra.

Theory and Applications of Categories [electronic only]

Iterative nondeterministic algebras

Banach Center Publications

On a characterization of the lattice of subsystems of a transition system.

International Journal of Mathematics and Mathematical Sciences

On covariety lattices

Discussiones Mathematicae - General Algebra and Applications

This paper shows basic properties of covariety lattices. Such lattices are shown to be infinitely distributive. The covariety lattice ${L}_{CV}\left(K\right)$ of subcovarieties of a covariety K of F-coalgebras, where F:Set → Set preserves arbitrary intersections is isomorphic to the lattice of subcoalgebras of a ${P}_{\kappa }$-coalgebra for some cardinal κ. A full description of the covariety lattice of Id-coalgebras is given. For any topology τ there exist a bounded functor F:Set → Set and a covariety K of F-coalgebras, such that...

On functions commuting with semigroups of transformations of algebras.

Siberian Mathematical Journal

On semidirect and two-sided semidirect products of finite $𝒥$trivial monoids

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

On the length of scales of computability potentials for $n$-element algebras.

Sibirskij Matematicheskij Zhurnal

On the solidity of general varieties of tree languages

Discussiones Mathematicae - General Algebra and Applications

For a class of hypersubstitutions 𝓚, we define the 𝓚-solidity of general varieties of tree languages (GVTLs) that contain tree languages over all alphabets, general varieties of finite algebras (GVFAs), and general varieties of finite congruences (GVFCs). We show that if 𝓚 is a so-called category of substitutions, a GVTL is 𝓚-solid exactly in case the corresponding GVFA, or the corresponding GVFC, is 𝓚-solid. We establish the solidity status of several known GVTLs with respect to certain categories...

On Varieties of Literally Idempotent Languages

RAIRO - Theoretical Informatics and Applications

A language L ⊆A* is literally idempotent in case that ua2v ∈ L if and only if uav ∈ L, for each u,v ∈ A*, a ∈ A. Varieties of literally idempotent languages result naturally by taking all literally idempotent languages in a classical (positive) variety or by considering a certain closure operator on classes of languages. We initiate the systematic study of such varieties. Various classes of literally idempotent languages can be characterized using syntactic methods. A starting example is the...

Page 1 Next