A counterexample to a conjecture concerning concatenation hierarchies
| KLÍMA, Ondřej and Jorge ALMEIDA. A counterexample to a conjecture concerning concatenation hierarchies. Information Processing Letters. Elsevier, vol. 110, No 1, p. 4 - 7. ISSN 0020-0190. 2009. |
|
Other formats:
BibTeX
LaTeX
RIS
|
| Basic information | |
|---|---|
| Original name | A counterexample to a conjecture concerning concatenation hierarchies |
| Name in Czech | Protiříklad k hypotéze ohledně konkatenačních hierarchií |
| Authors | KLÍMA, Ondřej (203 Czech Republic, guarantor) and Jorge ALMEIDA (620 Portugal). |
| Edition | Information Processing Letters, Elsevier, 2009, 0020-0190. |
| Other information | |
|---|---|
| Original language | English |
| Type of outcome | Article in a journal |
| Field of Study | 10101 Pure mathematics |
| Country of publisher | Netherlands |
| Confidentiality degree | is not subject to a state or trade secret |
| Impact factor | Impact factor: 0.764 |
| RIV identification code | RIV/00216224:14310/09:00029601 |
| Organization unit | Faculty of Science |
| UT WoS | 000272583400002 |
| Keywords in English | Formal languages; Regular languages; Concatenation hierarchies; Level two; Star-free languages |
| Tags | International impact, Reviewed |
| Changed by | Changed by: doc. Mgr. Ondřej Klíma, Ph.D., učo 3868. Changed: 30/3/2010 13:58. |
| Abstract |
|---|
| We give a counterexample to the conjecture which was originally formulated by Straubing in 1986 concerning a certain algebraic characterization of regular languages of level 2 in the Straubing Thérien concatenation hierarchy of star free languages. |
| Abstract (in Czech) |
|---|
| Nalezli jsme protipříklad k hypotéze, kterou zformuloval Straubing v roce 1986 a která se týkala jisté algebraické charakterizace regulárních jazyků stupně 2 v Straubing Thérien hierarchii bezhvězdičkových regulárních jazyků. |
| Links | |
|---|---|
| GA201/09/1313, research and development project | Name: Algebraické metody v teorii automatů a formálních jazyků II |
| Investor: Czech Science Foundation, Algebraic Methods in Automata and Formal Language Theory II | |
| MSM0021622409, plan (intention) | Name: Matematické struktury a jejich fyzikální aplikace |
| Investor: Ministry of Education, Youth and Sports of the CR, Mathematical structures and their physical applications | |
| 1M0545, research and development project | Name: Institut Teoretické Informatiky |
| Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science | |
PrintDisplayed: 20/4/2024 01:12