Locally Finite Languages
Finkel, Olivier
HAL, hal-00102491 / Harvested from HAL
We investigate properties of locally finite languages introduced by J-P. Ressayre. These languages are defined by locally finite sentences and generalize languages recognized by automata or defined by monadic second order sentences. We give many examples, showing that numerous context free languages are locally finite. Then we study closure properties of the family LOC of locally finite languages, and show that most undecidability results that hold for context free languages may be extended to locally finite languages. In a second part, we consider an extension of these languages to infinite and transfinite length words. We prove that each alpha-language which is recognized by a Büchi automaton ( where alpha is an infinite ordinal and alpha < omega^omega ) is defined by a locally finite sentence. This result, combined with a preceding one provides a generalization of Büchi's result about decidability of monadic second order theory of the structure (alpha , <).
Publié le : 2001-07-05
Classification:  [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO],  [MATH.MATH-LO]Mathematics [math]/Logic [math.LO]
@article{hal-00102491,
     author = {Finkel, Olivier},
     title = {Locally Finite Languages},
     journal = {HAL},
     volume = {2001},
     number = {0},
     year = {2001},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00102491}
}
Finkel, Olivier. Locally Finite Languages. HAL, Tome 2001 (2001) no. 0, . http://gdmltest.u-ga.fr/item/hal-00102491/