Umeå University's logo

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
Single-Rooted DAGs in Regular DAG Languages: Parikh Image and Path Languages
Stellenbosch University.
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
2017 (English)In: Proceedings of the 13th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+13) / [ed] M. Kuhlmann, T. Scheffler, Association for Computational Linguistics , 2017, p. 94-101Conference paper, Published paper (Refereed)
Abstract [en]

In a recent survey (Drewes, 2017) of results on DAG automata  some open problems are formulated for the case where the  DAG language accepted by a DAG automaton A is restricted to DAGs with a single root, denoted by L(A)u. Here we consider each of  those problems, demonstrating that: (i) the finiteness  of L(A)u is decidable, (ii) the path languages of L(A)u can be characterized in  terms of the string languages accepted by partially blind  multicounter automata, and  (iii) the Parikh image of L(A)u is semilinear.

Place, publisher, year, edition, pages
Association for Computational Linguistics , 2017. p. 94-101
Keywords [en]
DAG automaton, regular DAG language
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-137919OAI: oai:DiVA.org:umu-137919DiVA, id: diva2:1128882
Conference
13th International Workshop on Tree-Adjoining Grammar and Related Formalisms (TAG+13), Umeå, Sweden, September 4-6, 2017
Available from: 2017-07-31 Created: 2017-07-31 Last updated: 2019-06-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

PDF

Authority records

Björklund, HenrikDrewes, Frank

Search in DiVA

By author/editor
Björklund, HenrikDrewes, Frank
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 1180 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