LATPub686: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 15: | Zeile 15: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Language equations are equations where both the constants occurring in the | |Abstract=Language equations are equations where both the constants occurring in the equations and the solutions are formal languages. They have first been introduced in formal language theory, but are now also considered in other areas of computer science. In the present paper, we restrict the attention to language equations with one-sided concatenation, but in contrast to previous work on these equations, we allow not just union but all Boolean operations to be used when formulating them. In addition, we are not just interested in deciding solvability of such equations, but also in deciding other properties of the set of solutions, like its cardinality (finite, infinite, uncountable) and whether it contains least/greatest solutions. We show that all these decision problems are ExpTime-complete. | ||
equations and the solutions are formal languages. They have first | |||
been introduced in formal language theory, but are now also considered in | |||
other areas of computer science. In the present paper, we restrict the attention | |||
to language equations with one-sided concatenation, but in contrast to previous | |||
work on these equations, we allow not just union but all Boolean operations | |||
to be used when formulating them. In addition, we are not just interested in deciding | |||
solvability of such equations, but also in deciding other properties of the | |||
set of solutions, like its cardinality (finite, infinite, uncountable) | |||
and whether it contains least/greatest solutions. We show that all these | |||
decision problems are ExpTime-complete. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 45: | Zeile 34: | ||
year = {2006}, | year = {2006}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
On Language Equations with One-sided Concatenation
Franz BaaderFranz Baader, Alexander OkhotinAlexander Okhotin
Franz Baader, Alexander Okhotin
On Language Equations with One-sided Concatenation
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-06-01, 2006. LTCS-Report
On Language Equations with One-sided Concatenation
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-06-01, 2006. LTCS-Report
- KurzfassungAbstract
Language equations are equations where both the constants occurring in the equations and the solutions are formal languages. They have first been introduced in formal language theory, but are now also considered in other areas of computer science. In the present paper, we restrict the attention to language equations with one-sided concatenation, but in contrast to previous work on these equations, we allow not just union but all Boolean operations to be used when formulating them. In addition, we are not just interested in deciding solvability of such equations, but also in deciding other properties of the set of solutions, like its cardinality (finite, infinite, uncountable) and whether it contains least/greatest solutions. We show that all these decision problems are ExpTime-complete. - Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@techreport{ BaaderOkhotin-LTCS-06-01,
address = {Germany},
author = {Franz {Baader} and Alexander {Okhotin}},
institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
number = {LTCS-06-01},
title = {On Language Equations with One-sided Concatenation},
type = {LTCS-Report},
year = {2006},
}
