Infinite series-parallel posets: Logic and languages

被引：0
|
作者：
Kuske, D [1 ]
机构：
[1] Tech Univ Dresden, Inst Algebra, D-01062 Dresden, Germany
来源：
AUTOMATA LANGUAGES AND PROGRAMMING | 2000年 / 1853卷
关键词：
D O I：
暂无
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We show that a set of uniformly width-bounded infinite series-parallel pomsets is omega-series-rational iff it is axiomatizable in monadic second order logic iff it is omega-recognizable. This extends recent work by Lodaya and Well on sets of finite series-parallel pomsets in two aspects: It relates their notion of series-rationality to logical concepts, and it generalizes the equivalence of recognizability and series-rationality to infinite series-parallel pomsets.
引用
收藏
页码：648 / 662
页数：15
相关论文
共 50 条
  • [1] Logic and rational languages of scattered and countable series-parallel posets
    Amrane, Amazigh
    Bedon, Nicolas
    THEORETICAL COMPUTER SCIENCE, 2020, 809 (809) : 538 - 562
  • [2] Series-parallel languages on scattered and countable posets
    Bedon, Nicolas
    Rispal, Chloe
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (22) : 2356 - 2369
  • [3] Series-parallel languages on scattered and countable posets
    Bedon, Nicolas
    Rispal, Chloe
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS, 2007, 4708 : 477 - +
  • [4] Series-parallel posets: Algebra, automata and languages
    Lodaya, K
    Weil, P
    STACS 98 - 15TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, 1998, 1373 : 555 - 565
  • [5] THE PERMUTAHEDRON OF SERIES-PARALLEL POSETS
    SCHULZ, AS
    DISCRETE APPLIED MATHEMATICS, 1995, 57 (01) : 85 - 90
  • [6] THE PERMUTAHEDRON OF SERIES-PARALLEL POSETS
    VONARNIM, A
    FAIGLE, U
    SCHRADER, R
    DISCRETE APPLIED MATHEMATICS, 1990, 28 (01) : 3 - 9
  • [7] Series-parallel posets and the Tutte polynomial
    Gordon, G
    DISCRETE MATHEMATICS, 1996, 158 (1-3) : 63 - 75
  • [8] Retractions onto series-parallel posets
    Dalmau, Victor
    Krokhin, Andrei
    Larose, Benoit
    DISCRETE MATHEMATICS, 2008, 308 (11) : 2104 - 2114
  • [9] The setup polyhedron of series-parallel posets
    Schrader, R
    Wambach, G
    DISCRETE APPLIED MATHEMATICS, 1997, 79 (1-3) : 213 - 221
  • [10] N-FREE POSETS AS GENERALIZATIONS OF SERIES-PARALLEL POSETS
    HABIB, M
    JEGOU, R
    DISCRETE APPLIED MATHEMATICS, 1985, 12 (03) : 279 - 291
12345