Abstract
We associate a modal operator with each language belonging to a given class of regular languages and use the (reverse) wreath product of monoids with distinguished generators to characterize the expressive power of the resulting logic.
Supported in part by a grant from the National Foundation of Hungary for Scientific Research and by the Japan Society for the Promotion of Science.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
J. Almeida, Finite Semigroups and Universal Algebra, World Scientific, 1994.
A. Baziramwabo, P. McKenzie and D. Therien, Modular temporal logic, in: Proc. 1999 IEEE Conference LICS, Trento, Italy.
J. Cohen, J.-E. Pin and D. Perrin, On the expressive power of temporal logic, J. Computer and System Sciences, 46(1993), 271–294.
P. Dömösi and Z. Ésik, Critical classes for the α0-product, Theoretical Computer Science, 61(1988), 17–24.
S. Eilenberg, Automata, Languages, and Machines, vol. A and B, Academic Press, 1974 and 1976.
Z. Ésik and M. Ito, Temporal logic with cyclic counting and the degree of aperiodicity of finite automata, Acta Cybernetica, to appear.
Z. Ésik and K. G. Larsen, Regular languages definable by Lindström quantifiers, BRICS Reports, RS-02-20, April, 2002.
J. A. Kamp, Tense logic and the theory of linear order, Ph. D. Thesis, UCLA, 1968.
R. McNaughton and S. Papert, Counter-Free Automata, MIT Press, 1971.
A. Pnueli, The temporal logic of programs, in: Proc. 18th FOCS, Providence, RI, IEEE Press, 1977, 46–57.
H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Birkhauser, 1994.
H. Straubing, D. Therien and W. Thomas, Regular languages defined with generalized quantifiers, Information and Computation, 118(1995), 289–301.
D. Therien and Th. Wilke, Temporal logic and semidirect products: An effective characterization of the until hierarchy, DIMACS TR-96-28, 1996.
P. Wolper, Temporal logic can be more expressive, Information and Control, 56(1983), 72–99.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ésik, Z. (2003). Extended Temporal Logic on Finite Words and Wreath Product of Monoids with Distinguished Generators. In: Ito, M., Toyama, M. (eds) Developments in Language Theory. DLT 2002. Lecture Notes in Computer Science, vol 2450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45005-X_4
Download citation
DOI: https://doi.org/10.1007/3-540-45005-X_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40431-6
Online ISBN: 978-3-540-45005-4
eBook Packages: Springer Book Archive