The omega-inequality problem for concatenation hierarchies of star-free languages

ALMEIDA, Jorge, Ondřej KLÍMA and Michal KUNC. The omega-inequality problem for concatenation hierarchies of star-free languages. Forum Mathematicum. 2018, vol. 30, No 3, p. 663-679. ISSN 0933-7741. Available from: https://dx.doi.org/10.1515/forum-2016-0028.

Basic information

• Original name: The omega-inequality problem for concatenation hierarchies of star-free languages
• Authors: ALMEIDA, Jorge (620 Portugal), Ondřej KLÍMA (203 Czech Republic, guarantor, belonging to the institution) and Michal KUNC (203 Czech Republic, belonging to the institution).
• Edition: Forum Mathematicum, 2018, 0933-7741.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10101 Pure mathematics
• Country of publisher: Germany
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• Impact factor: Impact factor: 0.867
• RIV identification code: RIV/00216224:14310/18:00100967
• Organization unit: Faculty of Science
• Doi: http://dx.doi.org/10.1515/forum-2016-0028
• UT WoS: 000430908100008
• Keywords in English: Pseudovariety; relatively free profinite semigroup; ordered monoid; concatenation hierarchy; Straubing–Thérien hierarchy
• Tags: International impact, Reviewed

Abstract

The problem considered in this paper is whether an inequality of omega-terms is valid in a given level of a concatenation hierarchy of star-free languages. The main result shows that this problem is decidable for all (integer and half) levels of the Straubing-Therien hierarchy.

Links

• GA15-02862S, research and development project: Name: Aplikace algebry a kombinatoriky v teorii formálních jazyků

Investor: Czech Science Foundation