Key points are not available for this paper at this time.
Análogas às linguagens regulares de strings e árvores, as linguagens regulares de gráficos direcionados acíclicos (DAGs) são definidas na literatura. Embora chamadas de regulares, essas linguagens DAG são mais poderosas e, consequentemente, problemas padrão têm uma complexidade maior do que no caso de strings. Linguagens DAG determinísticas de cima para baixo e de baixo para cima são subclasses das linguagens DAG regulares. Refinamos essa hierarquia ao fornecer uma subclasse mais fraca das linguagens DAG determinísticas. Para uma gramática DAG gerando uma linguagem nesta nova classe de linguagem DAG, ou, equivalentemente, um autômato DAG reconhecendo-a, um autômato finito determinístico clássico (DFA) pode ser construído. Como resultado principal, fornecemos uma caracterização desta classe. A motivação por trás disso é a transferência de técnicas para linguagens regulares de strings para gráficos. Trivialmente, nossa classe restrita de linguagem DAG é fechada sob união e interseção. Isso permite a aplicação de algoritmos de minimização e hiperminimização conhecidos para DFAs. Essa alternativa de noção de regularidade se baseia na existência de um DFA para reconhecer uma linguagem DAG.
Yvo Ad Meeres (Ter,) estudou essa questão.