Abstract
We obtain a simple, purely game-theoretic characterization of Boolean grammars [A. Okhotin, Information and Computation, 194 (2004) 19-48]. In particular, we propose a two-player infinite game of perfect information for Boolean grammars, which is equivalent to their well-founded semantics. The game is directly applicable to the simpler classes of conjunctive and context-free grammars, and it offers a promising new connection between game theory and formal languages.
This work is supported by the 03EΔ 330 research project, implemented within the framework of the “Reinforcement Programme of Human Research Manpower” (ΠENEΔ) and co-financed by National and Community Funds (75% from E.U.-European Social Fund and 25% from the Greek Ministry of Development-General Secretariat of Research and Technology and from the private sector).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Galanaki, C., Rondogiannis, P., Wadge, W.: An Infinite-Game Semantics for Well-Founded Negation in Logic Programming. Annals of Pure and Applied Logic 151(2–3), 70–88 (2008)
Gale, D., Stewart, F.M.: Infinite Games with Perfect Information. Annals of Mathematical Studies 28, 245–266 (1953)
Kountouriotis, V., Nomikos, C., Rondogiannis, P.: Well-founded semantics for boolean grammars. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 203–214. Springer, Heidelberg (2006)
Martin, D.A.: Borel Determinacy. Annals of Mathematics 102, 363–371 (1975)
Moschovakis, Y.N.: Descriptive Set Theory. North-Holland, Amsterdam (1980)
Nomikos, C., Rondogiannis, P.: Locally Stratified Boolean Grammars. Information and Computation 206(9-10), 1219–1233 (2008)
Okhotin, A.: Conjunctive Grammars. Journal of Automata, Languages and Combinatorics 6(4), 519–535 (2001)
Okhotin, A.: Boolean Grammars. Information and Computation 194(1), 19–48 (2004)
Okhotin, A.: Nine open problems on conjunctive and Boolean grammars. TUCS Technical Report No 794, Turku Centre for Computer Science, Turku, Finland (November 2006)
Jeż, A., Okhotin, A.: Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol. 4649, pp. 168–181. Springer, Heidelberg (2007)
Przymusinska, H., Przymusinski, T.: Semantic Issues in Deductive Databases and Logic Programs. In: Banerji, R. (ed.) Formal Techniques in Artificial Intelligence: a Source-Book, pp. 321–367. North-Holland, Amsterdam (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kountouriotis, V., Nomikos, C., Rondogiannis, P. (2009). A Game-Theoretic Characterization of Boolean Grammars. In: Diekert, V., Nowotka, D. (eds) Developments in Language Theory. DLT 2009. Lecture Notes in Computer Science, vol 5583. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02737-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-02737-6_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02736-9
Online ISBN: 978-3-642-02737-6
eBook Packages: Computer ScienceComputer Science (R0)