Currently displaying 1 – 18 of 18

Showing per page

Order by Relevance | Title | Year of publication

Affine Parikh automata

Michaël CadilhacAlain FinkelPierre McKenzie — 2012

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

The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the , that extends the PA by having each transition induce an affine transformation on the PA registers, and the , that restricts the PA by forcing any two transitions on the same letter to affect the registers...

Affine Parikh automata

Michaël CadilhacAlain FinkelPierre McKenzie — 2012

RAIRO - Theoretical Informatics and Applications

The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the , that extends the PA by having each transition induce an affine transformation on the PA registers, and the , that restricts the PA by forcing any two transitions on...

Varieties with polynomially many models, I

Paweł M. IdziakRalph McKenzie — 2001

Fundamenta Mathematicae

A characterization of locally finite congruence modular varieties with the number of at most k-generated models being bounded from above by a polynomial in k is given. These are exactly the varieties polynomially equivalent to the varieties of unitary modules over a finite ring of finite representation type.

On the number of finite algebraic structures

Erhard AichingerPeter MayrR. McKenzie — 2014

Journal of the European Mathematical Society

We prove that every clone of operations on a finite set A , if it contains a Malcev operation, is finitely related – i.e., identical with the clone of all operations respecting R for some finitary relation R over A . It follows that for a fixed finite set A , the set of all such Malcev clones is countable. This completes the solution of a problem that was first formulated in 1980, or earlier: how many Malcev clones can finite sets support? More generally, we prove that every finite algebra with few...

Quasiequational theories of flat algebras

Jaroslav JežekM. MarótiR. McKenzie — 2005

Czechoslovak Mathematical Journal

We prove that finite flat digraph algebras and, more generally, finite compatible flat algebras satisfying a certain condition are finitely q -based (possess a finite basis for their quasiequations). We also exhibit an example of a twelve-element compatible flat algebra that is not finitely q -based.

Affine Parikh automata

Michaël CadilhacAlain FinkelPierre McKenzie — 2012

RAIRO - Theoretical Informatics and Applications

The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the , that extends the PA by having each transition induce an affine transformation on the PA registers, and the , that restricts the PA by forcing any two transitions on...

The weak extension property and finite axiomatizability for quasivarieties

Wiesław DziobiakMiklós MarótiRalph McKenzieAnvar Nurakunov — 2009

Fundamenta Mathematicae

We define and compare a selection of congruence properties of quasivarieties, including the relative congruence meet semi-distributivity, RSD(∧), and the weak extension property, WEP. We prove that if 𝒦 ⊆ ℒ ⊆ ℒ' are quasivarieties of finite signature, and ℒ' is finitely generated while 𝒦 ⊨ WEP, then 𝒦 is finitely axiomatizable relative to ℒ. We prove for any quasivariety 𝒦 that 𝒦 ⊨ RSD(∧) iff 𝒦 has pseudo-complemented congruence lattices and 𝒦 ⊨ WEP. Applying these results and other results...

Page 1

Download Results (CSV)