Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Families of locally testable languages
Autore:
Caron, P;
Indirizzi:
Univ Rouen, Lab Informat Fondamentale & Appl Rouen, F-76821 Mt St Aignan, France Univ Rouen Mt St Aignan France F-76821 uen, F-76821 Mt St Aignan, France
Titolo Testata:
THEORETICAL COMPUTER SCIENCE
fascicolo: 1-2, volume: 242, anno: 2000,
pagine: 361 - 376
SICI:
0304-3975(20000706)242:1-2<361:FOLTL>2.0.ZU;2-K
Fonte:
ISI
Lingua:
ENG
Soggetto:
ALGORITHM; AUTOMATA;
Keywords:
algorithms; automata; locally testable languages; regular languages;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
19
Recensione:
Indirizzi per estratti:
Indirizzo: Caron, P Univ Rouen, Lab Informat Fondamentale & Appl Rouen, F-76821 Mt StAignan, France Univ Rouen Mt St Aignan France F-76821 821 Mt St Aignan, France
Citazione:
P. Caron, "Families of locally testable languages", THEOR COMP, 242(1-2), 2000, pp. 361-376

Abstract

Kim, McNaughton and McCloskey have produced a polynomial time algorithm inorder to test if a deterministic automaton recognizes a locally testable language. We provide a characterization in terms of automata for the strictly locally testable languages and for the strongly locally testable languages, two subclasses of locally testable languages. These two characterizations lead us to polynomial time algorithms for testing these families of languages. (C) 2000 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 26/11/20 alle ore 19:59:54