Star-free languages are Church-Rosser congruential

DOI10.1016/j.tcs.2012.01.028zbMath1279.68147arXiv1111.4300OpenAlexW1975372170MaRDI QIDQ714818

Manfred Kufleitner, Pascal Weil, Volker Diekert

Publication date: 11 October 2012

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

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

zbMATH Keywords

string rewritingaperiodic monoidChurch-Rosser systemlocal divisorstar-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Parikh-reducing Church-Rosser representations for some classes of regular languages ⋮ Characterizing classes of regular languages using prefix codes of bounded synchronization delay ⋮ A survey on the local divisor technique ⋮ On the irreducibility of pseudovarieties of semigroups. ⋮ Locally countable pseudovarieties ⋮ Representations of relatively free profinite semigroups, irreducibility, and order primitivity

Cites Work

• Pure future local temporal logics are expressively complete for Mazurkiewicz traces
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Von Neumann regularity in Jordan triple systems
• The Krohn-Rhodes Theorem and Local Divisors
• An application of games to the completeness problem for formalized theories
• Church-Rosser Thue systems and formal languages
• On finite monoids having only trivial subgroups
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Star-free languages are Church-Rosser congruential