Progresso no problema generalizado de altura estelar?

A altura da estrela (generalizada) de um idioma é o agrupamento mínimo de estrelas Kleene necessárias para representar o idioma por uma expressão regular estendida. Lembre-se de que uma expressão regular estendida sobre um alfabeto finito $A$ satisfaz o seguinte:

(1) e um são estendidos expressões regulares para toda a ∈ $\emptyset, 1$$a$$a\in A$

(2) Para todas as expressões regulares estendidas ; E ∪ F , E F , E ∗ e E c são expressões regulares estendidas$E,F$
$E\cup F$$EF$$E^*$$E^c$

Uma frase do problema generalizado da altura da estrela é se existe um algoritmo para calcular a altura mínima generalizada da estrela. Com relação a esse problema, tenho algumas perguntas.

1. Houve algum progresso recente (ou interesse de pesquisa) em relação a esse problema? Sei há alguns anos que Pin Straubing e Thérien publicaram alguns trabalhos nessa área.

2. O problema de altura restrita das estrelas foi resolvido em 1988 por Hashiguchi, mas a versão generalizada (tanto quanto eu sei) ainda está aberta. Alguém tem alguma intuição de por que isso pode ser o caso?

Um link que pode ser útil é o seguinte: starheight

Com relação à sua segunda pergunta, uma explicação de por que o problema generalizado de altura estelar é menos acessível que o problema de altura estelar é o seguinte: O artigo seminal de Eggan, em 1963, já continha idiomas da (estrela ordinária) altura estelar , para cada k ≥ $k$$k\ge 0$ . Apenas alguns anos depois, McNaughton e, independentemente, Déjean e Schützenberger, encontraram exemplos sobre alfabetos binários. Isso deixou claro qual é o problema "." Durante os anos que se seguiram, houve um fluxo mais ou menos constante de resultados publicados na área do problema comum da altura das estrelas. Isso deu um corpo cada vez maior de exemplos publicados, contra-exemplos e fenômenos em torno desse problema.

Por outro lado, depois de cinquenta anos, não sabemos se existe alguma linguagem regular da altura das estrelas pelo menos duas. Portanto, nem sabemos se é necessário um procedimento de decisão. Essa "completa falta de exemplos" indica que é extremamente difícil entender esse problema.

Esta resposta é dedicada à memória de Janusz (John) Antoni Brzozowski, que faleceu em 24 de outubro de 2019.

John é certamente a pessoa que tornou os problemas de altura das estrelas tão famosos. De fato, em uma conferência em Santa Bárbara, em dezembro de 1979, ele apresentou uma seleção de seis problemas abertos sobre idiomas regulares e mencionou outros dois tópicos na conclusão de seu artigo [1]. Esses seis problemas em aberto foram, em ordem, altura da estrela, altura da estrela restrita, complexidade do grupo, remoção da estrela, regularidade de classes não contadas e otimização dos códigos de prefixo. Os outros dois tópicos foram o problema da limitação e a hierarquia de profundidade dos pontos.

Em junho de 2015, durante um conferência de um dia em homenagem aos seus 80 anos , apresentei dois artigos de pesquisa resumindo o estado da arte dessas questões [2, 3]. Em particular, você encontrará [2] informações detalhadas sobre os problemas de altura da estrela.

[1] JA Brzozowski, Problemas abertos sobre linguagens regulares , na teoria da linguagem formal. Perspectivas e problemas em aberto, Anais de um simpósio realizado em Santa Barbara, Califórnia, 10 a 14 de dezembro de 1979 [, RV Book (ed.), Pp. 23–47, Nova York Etc .: Academic Press, uma subsidiária da Harcourt Brace Jovanovich, Editores. XIII, 454 p., 1980.

[2] J.-É. PIN, Problemas abertos sobre idiomas comuns, 35 anos depois , Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. O papel da teoria na ciência da computação - ensaios dedicados a Janusz Brzozowski, World Scientific, 2017,

[3] J.-É. Pin, a hierarquia de profundidade de pontos, 45 anos depois . Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. O Papel da Teoria na Ciência da Computação - Ensaios Dedicados a Janusz Brzozowski, World Scientific, 2017.

A solução do problema restrito de altura da estrela inspirou a rica teoria das funções de custo regular (da Colcombet), que por sua vez ajudou a resolver outros problemas de decidibilidade e oferece novas ferramentas para atacar problemas abertos. Essa teoria ainda está em desenvolvimento e foi estendida a infinitas palavras, árvores finitas, árvores infinitas, com seu próprio conjunto de resultados profundos e problemas em aberto. Aqui está um artigo seminal da teoria e uma bibliografia , no site da Colcombet.

Portanto, embora não seja diretamente uma aplicação generalizada da altura da estrela, isso mostra que progredir em problemas aparentemente inúteis, como a altura da estrela, provavelmente significará uma melhor compreensão dos idiomas regulares e produzirá novos resultados em diferentes problemas.

Referência: Thomas Colcombet. "A teoria da estabilização monóide e funções de custo regulares". Em: ICALP 2009