Back to Search
Start Over
Series-Parallel Languages on Scattered and Countable Posets.
- Source :
- Mathematical Foundations of Computer Science 2007; 2007, p477-488, 12p
- Publication Year :
- 2007
-
Abstract
- We initiate a study on automata recognizing labelled posets constructed from scattered and countable linear orderings. More precisely, the class of labelled posets considered in this paper is the smallest containing letters, closed under finite parallel operation and sequential product indexed by all countable and scattered linear orderings. The first result of this paper establishes that those labelled posets are precisely the N-free ones. The second result is a Kleene-like theorem, which establishes that the class of languages of labelled posets accepted by branching automata is exactly the class of rational languages. This generalizes both the finite [9] and ω-labelled posets [2,6] cases, and the Kleene-like theorem on words on linear orderings [3]. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540744559
- Database :
- Complementary Index
- Journal :
- Mathematical Foundations of Computer Science 2007
- Publication Type :
- Book
- Accession number :
- 33196795
- Full Text :
- https://doi.org/10.1007/978-3-540-74456-6_43