Schützenberger and Eilenberg theorems for words on linear orderings

DOI10.1016/J.JCSS.2011.06.003MaRDI QIDQ414913zbMATH OpenOpenAlexFDO

Authors Nicolas Bedon, Chloé Rispal

Publication date 11 May 2012

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2011.06.003

zbMATH Keywords

first-order logicvarietiesinfinite wordsrecognizable languagesregular languageslinear orderingsrational languagesstar-free setstransfinite words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15)

Recommendations

• Developments in Language Theory
• Algebraic characterization of FO for scattered linear orderings
• scientific article; zbMATH DE number 1834651
• Automata on linear orderings
• Logic over words on denumerable ordinals

Cites work

• scientific article; zbMATH DE number 3915652 (Why is no real title available?)
• scientific article; zbMATH DE number 3924161 (Why is no real title available?)
• scientific article; zbMATH DE number 3959795 (Why is no real title available?)
• scientific article; zbMATH DE number 4037246 (Why is no real title available?)
• scientific article; zbMATH DE number 1189233 (Why is no real title available?)
• scientific article; zbMATH DE number 176766 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 798167 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 3329919 (Why is no real title available?)
• scientific article; zbMATH DE number 3341983 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• scientific article; zbMATH DE number 3096290 (Why is no real title available?)
• $ℵ_0$-categoricity of linear orderings
• Application of model theoretic games to discrete linear orders and finite automata
• Automata on linear orderings
• Automata, Semigroups and Recognizability of Words on Ordinals
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• Decision methods in the theory of ordinals
• Developments in Language Theory
• First-order logic and star-free sets
• Logic over words on denumerable ordinals
• On finite monoids having only trivial subgroups
• Star-free regular sets of ω-sequences
• Star-free sets of words on ordinals
• Unambiguous Büchi automata.
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(15)

• Atomicity and Well Quasi-Order for Consecutive Orderings on Words and Permutations
• First-order separation over countable ordinals
• scientific article; zbMATH DE number 1189233 (Why is no real title available?)
• C-sortable words as green mutation sequences
• On First-Order Fragments for Words and Mazurkiewicz Traces
• Developments in Language Theory
• Ranking and unranking fixed-density necklaces and Lyndon words
• Recognisable languages over monads
• Simon's theorem for scattered words
• On quasi orders of words and the confluence property
• Star-free sets of words on ordinals
• Algebraic characterization of FO for scattered linear orderings
• Nonexistence of a Kruskal-Katona type theorem for subword orders
• Logic over words on denumerable ordinals
• Lexicographically least words in the orbit closure of the Rudin-Shapiro word

This page was built for publication: Schützenberger and Eilenberg theorems for words on linear orderings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414913)