J 2018

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

ALMEIDA, Jorge, Ondřej KLÍMA and Michal KUNC

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

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10101 Pure mathematics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

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
Změněno: 1/3/2019 18:45, doc. Mgr. Ondřej Klíma, Ph.D.

Abstract

V originále

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
Displayed: 14/11/2024 14:03