FROM REGULAR WEIGHTED EXPRESSIONS TO FINITE AUTOMATA

In this article we generalize concepts of the position automaton and ZPC-structure to the regular $\mathbb{K}$ -expressions. We show that the extended ZPC-structure can be built in linear time w.r.t. the size of the $\mathbb{K}$ -expression and that the associated position automaton can be deduced f...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2004-10, Vol.15 (5), p.687-700
Main Authors: CHAMPARNAUD, JEAN-MARC, LAUGEROTTE, ÉRIC, OUARDI, FAISSAL, ZIADI, DJELLOUL
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article we generalize concepts of the position automaton and ZPC-structure to the regular $\mathbb{K}$ -expressions. We show that the extended ZPC-structure can be built in linear time w.r.t. the size of the $\mathbb{K}$ -expression and that the associated position automaton can be deduced from it in quadratic time.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054104002698