Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 3/2017

25.07.2016

On Boolean Closed Full Trios and Rational Kripke Frames

verfasst von: Georg Zetzsche, Dietrich Kuske, Markus Lohrey

Erschienen in: Theory of Computing Systems | Ausgabe 3/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study what languages can be constructed from a non-regular language L using Boolean operations and synchronous or non-synchronous rational transductions. If all rational transductions are allowed, one can construct the whole arithmetical hierarchy relative to L. In the case of synchronous rational transductions, we present non-regular languages that allow constructing languages arbitrarily high in the arithmetical hierarchy and we present non-regular languages that allow constructing only recursive languages. A consequence of the results is that aside from the regular languages, no full trio generated by a single language is closed under complementation. Another consequence is that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the definition of any language from the arithmetical hierarchy in the corresponding Kripke structure using multimodal logic.
Vorheriger Artikel Higher Randomness and Forcing with Closed Sets
Nächster Artikel New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
These latter closure properties are needed in order to realize projection and cylindrification of relations.
 
2
This is the only point were we need the recursiveness of L.
 
Literatur
1.
Barceló, P., Figueira, D., Libkin, L.: Graph Logics with Rational Relations and the Generalized Intersection Problem. In: Proceedings of the 27Th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2012), pp 115–124. IEEE Computer Society (2012)
2.
Bekker, W., Goranko, V.: Symbolic Model Checking of Tense Logics on Rational Kripke Models. In: Selected Papers of the International Conference on Infinity and Logic in Computation (ILC 2007), Lecture Notes in Computer Science, pp 2–20. Springer-Verlag (2009)
3.
4.
Blackburn, P., De Rijke, M., Venema, Y.: Modal logic. Cambridge University Press (2001)
5.
6.
Carayol, A., Morvan, C.: On Rational Trees. In: Proceedings of the 15Th Annual EACSL Conference on Computer Science Logic (CSL 2006), Volume 4207 of Lecture Notes in Computer Science, pp 225–239. Springer-Verlag (2006)
7.
Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. Inf. Comput. 176(1), 51–65 (2002)MathSciNetCrossRefMATH
8.
Chomsky, N., Schützenberger, M.-P.: The algebraic theory of context-free languages. North-Holland, Amsterdam (1963)CrossRefMATH
9.
10.
11.
Dassow, J., Păun, G.: Regulated rewriting in formal language theory. Springer-verlag, Berlin Heidelberg (1989)CrossRefMATH
12.
Elgot, C.C., Rabin, M.O.: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. J. Symb. Log. 31(2), 169–181 (1966)CrossRefMATH
13.
Engelfriet, J., Rozenberg, G.: Fixed point languages, equality languages, and representation of recursively enumerable languages. J. ACM 27(3), 499–518 (1980)MathSciNetCrossRefMATH
14.
15.
Frougny, C., Sakarovitch, J.: Synchronized rational relations of finite and infinite words. Theor. Comput. Sci. 108(1), 45–82 (1993)MathSciNetCrossRefMATH
16.
17.
Ginsburg, S., Goldstine, J.: Intersection-closed full AFL and the recursively enumerable languages. Inf. Control. 22(3), 201–231 (1973)MathSciNetCrossRefMATH
18.
Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theor. Comput. Sci. 7(3), 311–324 (1978)MathSciNetCrossRefMATH
19.
Harju, T., Karhumäki, J., Krob, D.: Remarks on Generalized Post Correspondence Problem. In: Proceedings of the 13Th International Symposium on Theoretical Aspects of Computer Science (STACS 1996), Volume 1046 of Lecture Notes in Computer Science, pp 39–48. Springer-Verlag (1996)
20.
Hartmanis, J., Hopcroft, J.: What makes some language theory problems undecidable. J. Comput. Syst. Sci. 4(4), 368–376 (1970)MathSciNetCrossRefMATH
21.
Haussler, D., Zeiger, H.P.: Very special languages and representations of recursively enumerable languages via computation histories. Inf. Control. 47(3), 201–212 (1980)MathSciNetCrossRefMATH
22.
Hopcroft, J.E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. Addison–Wesley, Reading, MA (1979)MATH
23.
Jantzen, M., Kurganskyy, A.: Refining the hierarchy of blind multicounter languages and twist-closed trios. Inf. Comput. 185(2), 159–181 (2003)MathSciNetCrossRefMATH
24.
Khoussainov, B., Nerode, A.: Automatic Presentations of Structures. In: LCC: International Workshop on Logic and Computational Complexity, Volume 960 of Lecture Notes in Computer Science, pp 367–392. Springer-Verlag (1995)
25.
Kleene, S. C.: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp 3–41. Princeton University Press, Princeton, NJ (1956)
26.
Lohrey, M., Zetzsche, G.: On Boolean closed full trios and rational Kripke frames. In: Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pp 530-541. Schloss DagstuhlLeibniz-Zentrum für Informatik, Dagstuhl, Germany (2014)
27.
Minsky, M.: Recursive unsolvability of Post’s problem of `tag’ and other topics in theory of Turing machines. Ann. Math. 74(3), 437–455 (1961)MathSciNetCrossRefMATH
28.
Morvan, C.: On rational graphs. In: Proceedings of the 3Rd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2000), Volume 2303 of Lecture Notes in Computer Science, pp 252–266. Springer-Verlag (2000)
29.
Morvan, C., Stirling, C.: Rational Graphs Trace Context-Sensitive Languages. In: Proceedings of the 26Th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001), Volume 2136 of Lecture Notes in Computer Science, pp 548–559. Springer-Verlag (2001)
30.
31.
Pin, J.-É., Sakarovitch, J.: Some Operations and Transductions that Preserve Rationality. In: Proceedings of the 6Th GI Conference, Volume 145 of Lecture Notes in Computer Science, pp 277–288. Springer-Verlag (1983)
32.
Rabinovich, A.: On decidability of monadic logic of order over the naturals extended by monadic predicates. Inf. Comput. 205, 870–889 (2007)MathSciNetCrossRefMATH
33.
Rabinovich, A., Thomas, W.: Decidable theories of the ordering of natural numbers with unary predicates. In: Proceedings of the 15th Annual EACSL Conference on Computer Science Logic (CSL 2006), volume 4207 of Lecture Notes in Computer Science, pp 562-574. Springer-Verlag, Berlin Heidelberg (2006)
34.
Reinhardt, K.: The “trio-zoo”–classes of formal languages generated from one language by rational transduction. Unpublished manuscript
35.
Render, E.: Rational monoid and semigroup automata. PhD Thesis, University of Manchester (2010)
36.
Rogers, H.: Theory of recursive functions and effective computability. McGraw-Hill (1968)
37.
Seibert, S.: Quantifier hierarchies over word relations. In: Proceedings of the 5Th Annual EACSL Conference on Computer Science Logic (CSL 1991), Volume 626 of Lecture Notes in Computer Science, pp 329–352. Springer-Verlag (1992)
38.
Semenov, A.: Decidability of monadic theories. In: Proceedings of the 11Th International Symposium on Mathematical Foundations of Computer Science (MFCS 1984), Volume 176 of Lecture Notes in Computer Science, pp 162–175. Springer-Verlag (1984)
39.
Thomas, W.: A Short Introduction to Infinite Automata. In: Proceedings of the 5Th International Conference on Developments in Language Theory (DLT 2001), Volume 2295 of Lecture Notes in Computer Science, pp 130–144. Springer-Verlag (2001)
40.
Zetzsche, G.: On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids. In: Proceedings of the 38Th International Colloquium on Automata, Languages and Programming (ICALP 2011), Volume 6756 of Lecture Notes in Computer Science, pp 222–233. Springer-Verlag (2011)
Metadaten
Titel
On Boolean Closed Full Trios and Rational Kripke Frames
verfasst von
Georg Zetzsche
Dietrich Kuske
Markus Lohrey
Publikationsdatum
25.07.2016
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 3/2017
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-016-9694-0

Weitere Artikel der Ausgabe 3/2017

Theory of Computing Systems 3/2017 Zur Ausgabe

OriginalPaper

A Solution to Wiehagen’s Thesis

OriginalPaper

Genericity of Weakly Computable Objects

OriginalPaper

New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings

OriginalPaper

Higher Randomness and Forcing with Closed Sets

News

Editor’s Note

OriginalPaper

2-Stack Sorting is Polynomial