umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Language Theoretic Properties of Regular DAG Languages
University of Würzburg.
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
2017 (English)In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, , 78 p.Article in journal (Refereed) Accepted
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.

Place, publisher, year, edition, pages
Elsevier, 2017. , 78 p.
Keyword [en]
DAG automaton, regular DAG language
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-137918OAI: oai:DiVA.org:umu-137918DiVA: diva2:1128879
Available from: 2017-07-31 Created: 2017-07-31 Last updated: 2017-08-21

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
In the same journal
Information and Computation
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Total: 24 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf