We show the existence of rational trace languages defined over direct products of free monoids that have inherent ambiguity of the order of log n and n 1/2 . This result is obtained by studying the relationship between trace languages and linear context-free grammars that satisfy a special unambiguity condition on the position of the last step of derivation.
Unambiguous Turn Position and Rational Trace Languages / M. GOLDWURM, K. WICH. - [s.l] : Universitaet Stuttgart, 2005.
Titolo: | Unambiguous Turn Position and Rational Trace Languages |
Autori: | |
Data di pubblicazione: | 2005 |
Parole Chiave: | Automata and Formal Languages; Trace Monoids; Inherent Ambiguity of rational trace languages; Linear Context-free Languages |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Enti collegati: | Institut fuer Informatik, Universitaet Stuttgart |
Citazione: | Unambiguous Turn Position and Rational Trace Languages / M. GOLDWURM, K. WICH. - [s.l] : Universitaet Stuttgart, 2005. |
Tipologia: | Working Paper |
Appare nelle tipologie: | 08 - Relazione interna o rapporto di ricerca |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
newklaus.pdf | Pre-print (manoscritto inviato all'editore) | Open Access Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.