Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Theory of Computing Systems
Published in: Theory of Computing Systems 3/2017

25-07-2016

On Boolean Closed Full Trios and Rational Kripke Frames

Authors: Georg Zetzsche, Dietrich Kuske, Markus Lohrey

Published in: Theory of Computing Systems | Issue 3/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

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.
previous article Higher Randomness and Forcing with Closed Sets
next article New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Footnotes
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.
 
Literature
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.
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.
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.
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)
Metadata
Title
On Boolean Closed Full Trios and Rational Kripke Frames
Authors
Georg Zetzsche
Dietrich Kuske
Markus Lohrey
Publication date
25-07-2016
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 3/2017
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-016-9694-0

Other articles of this Issue 3/2017

Theory of Computing Systems 3/2017 Go to the issue

OriginalPaper

Partition Expanders

OriginalPaper

On Symmetric Circuits and Fixed-Point Logics

OriginalPaper

Genericity of Weakly Computable Objects

OriginalPaper

A Solution to Wiehagen’s Thesis

News

Editor’s Note

OriginalPaper

2-Stack Sorting is Polynomial

Premium Partner

    Image Credits