Semantisches Browsen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
LATPub686
Abstract Language equations are equations where bot
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.
se decision problems are ExpTime-complete.  +
Archivierungsnummer LTCS-06-01  +
Author Franz Baader + , Alexander Okhotin +
BibTex
@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},
}
Bibtype Techreport  +
Download BaaderOkhotin-LTCS-06-01.pdf  +
ErsterAutorNachname Baader  +
ErsterAutorVorname Franz  +
Forschungsgruppe Automatentheorie +
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.  +
Publication text Franz Baader, Alexander Okhotin<br />
Franz Baader, Alexander Okhotin<br /> '''[[LATPub686|On Language Equations with One-sided Concatenation]]''' <br />__NOTOC__Technical Report, ''Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology'', volume LTCS-06-01, 2006. ''LTCS-Report''<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[LATPub686|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:BaaderOkhotin-LTCS-06-01.pdf|Download]]
ia:BaaderOkhotin-LTCS-06-01.pdf|Download]]  +
Publication text en Franz Baader, Alexander Okhotin<br />
Franz Baader, Alexander Okhotin<br /> '''[[LATPub686/en|On Language Equations with One-sided Concatenation]]''' <br />__NOTOC__Technical Report, ''Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology'', volume LTCS-06-01, 2006. ''LTCS-Report''<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[LATPub686|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:BaaderOkhotin-LTCS-06-01.pdf|Download]]
ia:BaaderOkhotin-LTCS-06-01.pdf|Download]]  +
Reviewed 0  +
Title On Language Equations with One-sided Concatenation  +
Typ LTCS-Report  +
Type techreport  +
Year 2006  +
Hat Abfrage
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
LATPub686 + , LATPub686 + , LATPub686 + , LATPub686 + , LATPub686 + , LATPub686 +
Kategorien Techreport , Publikation
Zuletzt geändert
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
25 März 2015 14:34:09  +
verstecke Attribute die hierhin verlinken 
LATPub686/en + Weiterleitungsseite
 

 

Bitte den Namen einer Seite angeben, um mit dem Browsen zu beginnen.