Language theoretic properties of regular DAG languages

Blum, Johannes; Drewes, Frank

Language theoretic properties of regular DAG languages

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2019

Autor:innen

Blum, Johannes

Drewes, Frank

DOI (zitierfähiger Link)

https://doi.org/10.1016/j.ic.2017.07.011

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

Information and Computation. 2019, 265, pp. 57-76. ISSN 0890-5401. Available under: doi: 10.1016/j.ic.2017.07.011

Zusammenfassung

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.

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

BLUM, Johannes, Frank DREWES, 2019. Language theoretic properties of regular DAG languages. In: Information and Computation. 2019, 265, pp. 57-76. ISSN 0890-5401. Available under: doi: 10.1016/j.ic.2017.07.011

BibTex

@article{Blum2019-04Langu-45221,
  year={2019},
  doi={10.1016/j.ic.2017.07.011},
  title={Language theoretic properties of regular DAG languages},
  volume={265},
  issn={0890-5401},
  journal={Information and Computation},
  pages={57--76},
  author={Blum, Johannes and Drewes, Frank}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/45221">
    <dc:creator>Drewes, Frank</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:title>Language theoretic properties of regular DAG languages</dcterms:title>
    <dc:contributor>Drewes, Frank</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/45221"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-27T08:36:10Z</dcterms:available>
    <dc:contributor>Blum, Johannes</dc:contributor>
    <dcterms:abstract xml:lang="eng">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.</dcterms:abstract>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dcterms:issued>2019-04</dcterms:issued>
    <dc:creator>Blum, Johannes</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-27T08:36:10Z</dc:date>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja

Begutachtet

Unbekannt