Commutative one-counter languages are regular

DOI10.1016/0022-0000(84)90013-8MaRDI QIDQ800097zbMATHOpenAlexFDO

Authors Michel Latteux, Grzegorz Rozenberg

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/0022-0000(84)90013-8

zbMATH Keywords

regular languagescommutative languagescommutative closureone-counter languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3936538
• On the commutative equivalence of bounded context-free and regular languages: the semi-linear case
• scientific article; zbMATH DE number 3845857
• On the commutative equivalence of bounded context-free and regular languages: the code case
• Every commutative quasirational language is regular

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3780588 (Why is no real title available?)
• scientific article; zbMATH DE number 3602693 (Why is no real title available?)
• scientific article; zbMATH DE number 3621144 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Langages à un compteur
• On the usefulness of bifaithful rational cones
• Ordering by Divisibility in Abstract Algebras
• Pumping Lemmas for Regular Sets

Cited in

(15)

• Well quasi-orders and regular languages
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
• On (left) partial shuffle
• scientific article; zbMATH DE number 4001505 (Why is no real title available?)
• Every commutative quasirational language is regular
• Commutative languages and their composition by consensual methods
• State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
• Rational languages and the Burnside problem
• Jumping finite automata: characterizations and complexity
• Scattered deletion and commutativity
• State complexity bounds for the commutative closure of group languages
• On the Hurwitz product of formal power series and automata
• scientific article; zbMATH DE number 3986658 (Why is no real title available?)
• Characterization and complexity results on jumping finite automata
• On total regulators generated by derivation relations

This page was built for publication: Commutative one-counter languages are regular

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