Star-free languages are Church-Rosser congruential

DOI10.1016/j.tcs.2012.01.028zbMath1279.68147arXiv1111.4300MaRDI 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 rewriting; aperiodic monoid; Church-Rosser system; local divisor; star-free language

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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