Finitely generated ideal languages and synchronizing automata

We study representations of ideal languages by means of strongly connected synchronizing automata. For every finitely generated ideal language L we construct such an automaton with at most 2^n states, where n is the maximal length of words in L. Our constructions are based on the De Bruijn graph.

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-05
Main Authors: Gusev, Vladimir V, Maslennikova, Marina I, Pribavkina, Elena V
Format: Article
Language:English
Subjects:
Graph theory
Languages
Synchronism
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study representations of ideal languages by means of strongly connected synchronizing automata. For every finitely generated ideal language L we construct such an automaton with at most 2^n states, where n is the maximal length of words in L. Our constructions are based on the De Bruijn graph.
ISSN:2331-8422