Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

2 2021

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: congruence lattices

Sortuj według:

Ogranicz wyniki do:

On Rough Approximations of Languages under Infinite Index Indiscernibility Relations

Martín Torres Gabriela

Fundamenta Informaticae

2021

Vol. 179, nr 3

275--293

In the paper [13] Păun, Polkowski and Skowron introduce several indiscernibility relations among strings that are infinite index equivalence or tolerance relations, and study lower and upper rough approximations of languages defined by them. In this paper we develop a further study of some of these indiscernibility relations among strings. We characterize the classes defined by them, and the rough approximations of general and context free languages under them. We also compare some of the rough approximations these relations produce to the ones given by the congruences defining testable, reverse testable, locally testable, piecewise testable and commutative languages. Those yield languages belonging to that families. Next, we modify some of the relations to obtain congruences, and study the families of languages the rough approximations under them give rise to. One of these modificated relations turns out to be the k-abelian congruence, that was defined by J. Karhumäki in [7], in the context of combinatorics on words. We show that it defines a pseudo-principal +-variety, a term defined in [9]. Our results in that work are then applied to determine when a given language has a best upper approximation in that family. Finally, we make some comments on the accuracy of the rough approximations obtained in each case.

A Congruence-Based Perspective on Finite Tree Automata

Ganty Pierre, Gutiérrez Elena, Valero Pedro

Fundamenta Informaticae

2021

Vol. 184, nr 1

1-47

We provide new insights on the determinization and minimization of tree automata using congruences on trees. From this perspective, we study a Brzozowski's style minimization algorithm for tree automata. First, we prove correct this method relying on the following fact: when the automata-based and the language-based congruences coincide, determinizing the automaton yields the minimal one. Such automata-based congruences, in the case of word automata, are defined using pre and post operators. Now we extend these operators to tree automata, a task that is particularly challenging due to the reduced expressive power of deterministic top-down (or equivalently co-deterministic bottom-up) automata. We leverage further our framework to offer an extension of the original result by Brzozowski for word automata.