Long words: The theory of concatenation and \(\omega\)-power

DOI10.1016/S0304-3975(00)00040-2zbMath0972.68106MaRDI QIDQ5941292

Stephen L. Bloom, Christian Choffrut

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

-powerAxiomatizationChoueka automataSeries product

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (12)

Equational Theories of Scattered and Countable Series-Parallel Posets ⋮ Two equational theories of partial words ⋮ Axiomatizing omega and omega-op powers of words ⋮ An automata-theoretic approach to the word problem for \(\omega\)-terms over R ⋮ Büchi context-free languages ⋮ A note on ordinal DFAs ⋮ The equational theory of regular words ⋮ ALGEBRAIC LINEAR ORDERINGS ⋮ ON CONTEXT-FREE LANGUAGES OF SCATTERED WORDS ⋮ The ordinal generated by an ordinal grammar is computable ⋮ Test sets for equality of terms in the additive structure of ordinals augmented with right multiplication by \(\omega\) ⋮ Axiomatizing the subsumption and subword preorders on finite and infinite partial words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Free shuffle algebras in language varieties
• Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• Nonfinite axiomatizability of shuffle inequalities

This page was built for publication: Long words: The theory of concatenation and \(\omega\)-power