Language theoretic properties of regular DAG languages

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

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

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

<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/rdf/resource/123456789/45221"> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-27T08:36:10Z</dc:date> <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> <dc:contributor>Blum, Johannes</dc:contributor> <dc:creator>Blum, Johannes</dc:creator> <dc:contributor>Drewes, Frank</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-27T08:36:10Z</dcterms:available> <dc:language>eng</dc:language> <dcterms:title>Language theoretic properties of regular DAG languages</dcterms:title> <dcterms:issued>2019-04</dcterms:issued> <dc:creator>Drewes, Frank</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/45221"/> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account