<div class="csl-bib-body">
<div class="csl-entry">Kuich, W., Droste, M., & Dziadek, S. (2019). Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata. In A. Chattopadhyay & P. Gastin (Eds.), <i>39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)</i> (pp. 38:1-38:14). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2019.38</div>
</div>
-
dc.identifier.isbn
978-3-95977-131-3
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/41712
-
dc.description.abstract
In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Here, we investigate weighted context-free languages of infinite words, a generalization of omega-context-free languages (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Schützenberger 1963). As in the theory of formal grammars, these weighted languages, or omega-algebraic series, can be represented as solutions of mixed omega-algebraic systems of equations and by weighted omega-pushdown automata. In our first main result, we show that mixed omega-algebraic systems can be transformed into Greibach normal form. Our second main result proves that simple omega-reset pushdown automata recognize all omega-algebraic series that are a solution of an omega-algebraic system in Greibach normal form. Simple reset automata do not use epsilon-transitions and can change the stack only by at most one symbol. These results generalize fundamental properties of context-free languages to weighted languages.
en
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
Weighted omega-Context-Free Grammars
-
dc.subject
Algebraic Systems
-
dc.subject
Greibach Normal Form
-
dc.subject
Weighted Automata
-
dc.subject
omega-Pushdown Automata
-
dc.title
Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata
en
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
-
dc.relation.isbn
978-3-95977-131-3
-
dc.relation.issn
1868-8969
-
dc.description.startpage
38:1
-
dc.description.endpage
38:14
-
dc.type.category
Full-Paper Contribution
-
dc.publisher.place
Schloss Dagstuhl GmbH, Wadern, Deutschland
-
tuw.booktitle
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
-
tuw.container.volume
150
-
tuw.book.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
tuw.relation.publisher
Schloss Dagstuhl–Leibniz-Zentrum für Informatik
-
tuw.relation.publisherplace
Dagstuhl, Germany
-
tuw.publication.orgunit
E104-02 - Forschungsbereich Computational Logic
-
tuw.publisher.doi
10.4230/LIPIcs.FSTTCS.2019.38
-
dc.description.numberOfPages
14
-
tuw.event.name
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - FSTTCS 2019
-
tuw.event.startdate
11-12-2019
-
tuw.event.enddate
13-12-2019
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Dagstuhl
-
tuw.event.country
DE
-
tuw.event.presenter
Kuich, Werner
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1010
-
wb.facultyfocus
Diskrete Mathematik und Geometrie
de
wb.facultyfocus
Discrete Mathematics and Geometry
en
wb.facultyfocus.faculty
E100
-
item.grantfulltext
none
-
item.cerifentitytype
Publications
-
item.cerifentitytype
Publications
-
item.openairetype
Konferenzbeitrag
-
item.openairetype
Inproceedings
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cf
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cf
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E104 - Institut für Diskrete Mathematik und Geometrie