umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Language Theoretic Properties of Regular DAG Languages
University of Würzburg.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0001-7349-7693
2019 (engelsk)Inngår i: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 265, s. 78s. 57-76Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

We study sets of directed acyclic graphs, called regular DAG languages, which are accepted by a recently introduced type of DAG automata motivated by current developments in natural language processing. We prove (or disprove) closure properties, establish pumping lemmata, characterize finite regular DAG languages, and show that "unfolding" turns regular DAG languages into regular tree languages, which implies a linear growth property and the regularity of the path languages of regular DAG languages. Further, we give polynomial decision algorithms for the emptiness and finiteness problems, and show that deterministic DAG automata can be minimized and tested for equivalence in polynomial time.

sted, utgiver, år, opplag, sider
Elsevier, 2019. Vol. 265, s. 78s. 57-76
Emneord [en]
DAG automaton, regular DAG language
HSV kategori
Forskningsprogram
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-137918DOI: 10.1016/j.ic.2017.07.011ISI: 000458499800003OAI: oai:DiVA.org:umu-137918DiVA, id: diva2:1128879
Tilgjengelig fra: 2017-07-31 Laget: 2017-07-31 Sist oppdatert: 2019-04-16bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Drewes, Frank

Søk i DiVA

Av forfatter/redaktør
Drewes, Frank
Av organisasjonen
I samme tidsskrift
Information and Computation

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 1618 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf