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

DOI10.1007/S00233-011-9357-ZzbMATH Open1261.20075OpenAlexW2054241966MaRDI QIDQ444643FDOQ444643

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

Recommendations

• Normal forms under Simon's congruence
• REFLEXIVE RELATIONS, EXTENSIVE TRANSFORMATIONS AND PIECEWISE TESTABLE LANGUAGES OF A GIVEN HEIGHT
• Testing Simon's congruence
• Hierarchies of piecewise testable languages
• Hierarchies of Piecewise Testable Languages

zbMATH Keywords

semigroupsbases of identitiesword problemnormal form theoremsfree syntactic monoidspiecewise testable languagespseudovarieties of finite monoids

Mathematics Subject Classification ID

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

Cites Work

• Complexity of some problems from the theory of automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equations and monoid varieties of dot-depth one and two
• Games, equations and the dot-depth hierarchy

Cited In (9)

• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• Syntactic monoids and word problems.
• On the index of Simon's congruence for piecewise testability
• Hierarchies of Piecewise Testable Languages
• Irreducible ambibuities in monoids of words
• Title not available (Why is that?)
• REFLEXIVE RELATIONS, EXTENSIVE TRANSFORMATIONS AND PIECEWISE TESTABLE LANGUAGES OF A GIVEN HEIGHT
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• Normal forms under Simon's congruence

This page was built for publication: On the word problem for syntactic monoids of piecewise testable languages.

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