Logic and rational languages of scattered and countable series-parallel posets

DOI10.1007/978-3-030-13435-8_20zbMath1425.03013arXiv1912.10240OpenAlexW3002995990WikidataQ126329613 ScholiaQ126329613MaRDI QIDQ5919278

Nicolas Bedon, Amazigh Amrane

Publication date: 4 December 2019

Published in: Theoretical Computer Science, Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.10240

zbMATH Keywords

monadic second-order logicPresburger arithmeticautomata and logicbranching automataseries-parallel posetsseries-parallel rational languagestransfinite N-free posets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Related Items

Equational Theories of Scattered and Countable Series-Parallel Posets, Logic and rational languages of scattered and countable series-parallel posets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Schützenberger and Eilenberg theorems for words on linear orderings
• Series-parallel languages on scattered and countable posets
• Automata on linear orderings
• Logic and rational languages of words indexed by linear orderings
• Series-parallel languages and the bounded-width property
• Rationality in algebras with a series operation
• Towards a language theory for infinite N-free pomsets.
• Semigroups, Presburger formulas, and languages
• Rational sets in commutative monoids
• Tree acceptors and some of their applications
• Algebraic Characterization of FO for Scattered Linear Orderings
• Weak Second‐Order Arithmetic and Finite Automata
• Limited Set quantifiers over Countable Linear Orderings
• Logic and Bounded-Width Rational Languages of Posets over Countable Scattered Linear Orderings
• Decision Problems of Finite Automata Design and Related Arithmetics
• The Recognition of Series Parallel Digraphs
• Complementation of Branching Automata for Scattered and Countable N-Free Posets
• On Context-Free Languages
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Finite automata and the logic of one-place predicates
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Logic and Branching Automata
• Logic and rational languages of scattered and countable series-parallel posets