On the word problem for syntactic monoids of piecewise testable languages.

DOI10.1007/s00233-011-9357-zzbMath1261.20075OpenAlexW2054241966MaRDI QIDQ444643

Csaba Szabó, Gabriella Pluhár, András Pongrácz, Péter Pál Pach, Kamilla Kátai-Urbán

Publication date: 16 August 2012

Published in: Semigroup Forum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00233-011-9357-z

zbMATH Keywords

semigroupsword problembases of identitiesnormal form theoremsfree syntactic monoidspiecewise testable languagespseudovarieties of finite monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Unnamed Item, Normal forms under Simon's congruence, Nearly \(k\)-universal words -- investigating a part of Simon's congruence, On the index of Simon's congruence for piecewise testability, Nearly \(k\)-universal words -- investigating a part of Simon's congruence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equations and monoid varieties of dot-depth one and two
• Games, equations and the dot-depth hierarchy
• Complexity of some problems from the theory of automata