Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra
Подождите немного. Документ загружается.
Algebraic classifications of regular tree languages 427
[9] S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Springer-Verlag,
New York, 1981.
[10] P. M. Cohn, Universal Algebra, D. Reidel, Dordrecht, 2nd revised ed., 1981.
[11] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tom-
masi, Tree Automata and Applications, http://www.grappa.univ-lille3.fr/tata/
(project under development since 1997).
[12] B. Courcelle, A representation of trees by languages I, Theoret. Comput. Sci. 6 (1978),
255–279.
[13] B. Courcelle, On recognizable sets and tree-automata, in: Resolution of Equations in
Algebraic Structures, Vol. 1 (M. Nivat and H. A
¨
it-Kaci, eds.), Academic Press, New
York, 1989, 93–126.
[14] B. Courcelle, Basic notions of universal algebra for language theory and graph gram-
mars, Theoret. Comput. Sci. 163 (1996), 1–54.
[15] K. Denecke and S. L. Wismath, Universal Algebra and Applications in Theoretical
Computer Science, Chapman & Hall/CRC, Boca Raton, 2002.
[16] J. Doner, Tree acceptors and some of their applications, J. Comput. System Sci. 4
(1970), 406–451.
[17] S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, New York,
1974.
[18] S. Eilenberg, Automata, Languages, and Machines, Vol. B, Academic Press, New York,
1976.
[19] S. Eilenberg and M.-P. Sch¨utzenberger, On pseudovarieties, Advances in Mathematics
19 (1976), 413–418.
[20] S. Eilenberg and J. B. Wright, Automata in general algebras, Information and Com-
putation 11 (1967), 452–470.
[21] Z.
´
Esik, Definite tree automata and their cascade composition, Publ. Math. Debrecen
48, 3–4 (1996), 243–261.
[22] Z.
´
Esik, A variety theory for trees and theories, Publ. Math. Debrecen 54 (1999), 711–
762.
[23] Z.
´
Esik and P. Weil, On certain logically defined regular tree languages, in: Foundations
of Software Technology and Theoretical Computer Science, Lecture Notes in Comput.
Sci. 2914, Springer, Berlin 2003, 195–207.
[24] F. G´ecseg and B. Imreh, On a special class of tree automata, in: Automata, Languages
and Programming Systems, Dept. Math., K. Marx University of Economics, Budapest,
1988, 141–152.
428 M. Steinby
[25] F. G´ecseg and B. Imreh, On monotone automata and monotone languages, J. Au-
tomata, Languages and Combinatorics 7 (2002), 71–82.
[26] F. G´ecseg and B. Imreh, On definite and nilpotent DR tree languages, J. Automata,
Languages and Combinatorics 9 (2004), 55–60.
[27] F. G´ecseg and M. Steinby, Minimal ascending tree automata, Acta Cybernetica 4 (1978),
37–44.
[28] F. G´ecseg and M. Steinby, Tree automata,Akad´emiai Kiad´o, Budapest, 1984.
[29] F. G´ecseg and M. Steinby, Tree languages, in: Handbook of Formal Languages, Vol. 3
(G. Rozenberg and A. Salomaa, eds.), Springer-Verlag, Berlin, 1997, 1–69.
[30] F. G´ecseg and M. Steinby, Minimal recognizers and syntactic monoids of DR tree
languages, in: Words, Semigroups and Transductions (M. Ito, G. Paun, and S. Yu,
eds.), World Scientific, Singapore, 2001, 155–167.
[31] A. Ginzburg, About some properties of definite, reverse-definite and related automata,
IEEE Trans. Electronic Computers EC-15 (1966), 809–810.
[32] G. Gr¨atzer, Universal Algebra, Springer-Verlag, New York, 2nd revised ed., 1979.
[33] U. Heuter, Definite tree languages, Bulletin of the EATCS 35 (1988), 137–142.
[34] U. Heuter, Generalized definite tree languages, in: Math. Found. of Comput. Sci.,
Lecture Notes in Comput. Sci. 379, Springer, Berlin, 1989, 270–280.
[35] U. Heuter, Zur Klassifizierung regul¨arer Baumsprachen, Dissertation, Faculty of Natu-
ral Science, RWTH, Aachen, 1989.
[36] U. Heuter, First-order properties of trees, star-free expressions and aperiodicity, RAIRO
Theoret. Informatics and Appl. 25 (1991) 125–145.
[37] J. M. Howie, Automata and Languages, Clarendon Press, Oxford, 1991.
[38] E. Jurvanen, The Boolean closure of DR-recognizable tree languages, Acta Cybernetica
10 (1992), 255–272.
[39] E. Jurvanen, On tree languages defined by deterministic root-to-frontier recognizers,
Ph.D. thesis, University of Turku, 1995.
[40] E. Jurvanen, A. Potthoff, and W. Thomas, Tree languages recognizable by regular
frontier check, in: Developments in language theory (G. Rozenberg and A. Salomaa,
eds.), World Scientific, Singapore 1994, 3–17.
[41] A. Kelarev and O. Sokratova, Directed graphs and syntactic algebras of tree languages,
J. Automata, Languages and Combinatorics 6 (2001), 305–311.
[42] S. C. Kleene, Representation of events in nerve nets and finite automata, in: Automata
Studies (C. E. Shannon and J. McCarthy, eds.), Princeton University Press, Princeton,
NJ, 1956, 3–42.
Algebraic classifications of regular tree languages 429
[43] T. Knuutila, Inference of k-testable tree languages, in: Advances in Structural and
Syntactic Pattern Recognition (H. Bunke, ed.), World Scientific, Singapore 1992, 109–
120.
[44] D. C. Kozen, Automata and Computability, Springer, New York 1997.
[45] G. Lallement, Semigroups and combinatorial applications, John Wiley & Sons, New
York, 1979.
[46] D. L´opez, Inferencia de lenguajes de ´arboles, Ph.D. thesis, Universida Polit´ecnica de
Valencia, 2003.
[47] M. Magidor and G. Moran, Finite automata over finite trees, Technical Report 30,
Hebrew University, Jerusalem, 1969.
[48] T. S. E. Maibaum, A generalized approach to formal languages, J. Comput. Systems
Sci. 8 (1974), 409–439.
[49] R. N. McKenzie, G. F. McNulty, and W. F. Taylor, Algebras, Lattices, Varieties, Vol. I,
Wadsworth & Brooks/Cole, Monterey, CA, 1987.
[50] R. McNaughton, and S. Papert, Counter-free automata, MIT Press, Cambridge, MA,
1971.
[51] K. Meinke and J. V. Tucker, Universal algebra, in: Handbook of Logic in Computer
Science, Vol. 1 (S. Abramsky, D. Gabbay, and T. S. Maibaum, eds.), Clarendon Press,
Oxford 1992, 189–411.
[52] J. Mezei and J. B. Wright, Algebraic automata and context-free sets, Information and
Control 11 (1967), 3–29.
[53] M. Nivat and A. Podelski, Tree monoids and recognizability of sets of finite trees, in:
Resolution of Equations in Algebraic Theories, Vol. 1 (H. A
¨
it-Kaci and M. Nivat, eds.),
Academic Press, Boston, 1989, 351–367.
[54] M. Nivat and A. Podelski, Definite tree automata (cont’d), Bull. EATCS 38 (1989),
186–190.
[55] P. P´eladeau and A. Podelski, On reverse and general definite tree languages, in: Au-
tomata, Languages and Programming, Lecture Notes in Comput. Sci. 623, Springer,
Berlin, 1992, 150–161.
[56] M. Perles, M. O. Rabin, and E. Shamir, The theory of definite automata, IEEE Trans.
Electronic Computers EC-12 (1963), 233–243.
[57] T. Petkovi´c, Varieties of automata and semigroups (in Serbian), Ph.D. thesis, University
of Niˇs, 1998.
[58] T. Petkovi´c, M.
´
Ciri´c, and S. Bogdanovi´c, Characteristic semigroups of directable au-
tomata, in: Proceedings of Developments in Language Theory 2002 (M. Ito and M.
Toyama, eds.), Lecture Notes in Computer Science 2450, Springer, Berlin, 2003, 417–
428.
430 M. Steinby
[59] T. Petkovi´c, M.
´
Ciri´c, and S. Bogdanovi´c, Unary algebras, semigroups and congruences
on free semigroups, Theoret. Comput. Sci. 324 (2004), 87–105.
[60] T. Petkovi´c and S. Salehi, Positive varieties of tree languages, TUCS Technical Report
622, Turku Centre for Computer Science, Turku, 2004.
[61] V. Piirainen, Monotone algebras, R-trivial monoids and a variety of tree languages,
Bulletin of the EATCS 84 (2004), 189–194.
[62] V. Piirainen, Piecewise testable tree languages, TUCS Technical Report 634,Turku
Centre for Computer Science, Turku 2004.
[63] J.-E. Pin, Varieties of formal languages, North Oxford Academic Publ., London, 1986.
[64] J.-E. Pin, Syntactic semigroups, in: Handbook of Formal Languages, Vol. 1 (G. Rozen-
berg, A. Salomaa, eds.), Springer, Berlin, 1997, 679–746.
[65] A. Podelski, A monoid approach to tree automata, in: Tree Automata and Languages
(M. Nivat and A. Podelski, eds.), Elsevier Science Publishers, Amsterdam, 1992, 41–56.
[66] A. Potthoff, Logische Klassifizierung regul¨arer Baumsprachen, Bericht Nr. 9410, Insti-
tut f¨ur Informatik und Praktische Mathematik, Christian-Albrechts-Universit¨at, Kiel,
1994.
[67] A. Potthoff, Modulo counting quantifiers over finite trees, Theor. Comput. Sci. 126
(1994), 97–112.
[68] A. Potthoff, First-order logic on finite trees. Theory and Practice of Software Develop-
ment (P. D. Mosses et al., eds.), Lecture Notes in Comput. Sci. 915, Springer, Berlin,
1995, 125–139.
[69] A. Potthoff and W. Thomas, Regular tree languages without unary symbols are star-
free, Fundamentals of Computation Theory, Lecture Notes in Computer Science 710,
Springer, Berlin, 1993, 396–405.
[70] J. Reiterman, The Birkhoff theorem for finite algebras, Algebra Universalis 14 (1985),
1–10.
[71] S. Salehi, Varieties of tree languages definable by syntactic monoids, TUCS Technical
Report 619, Turku Centre for Computer Science, Turku 2004.
[72] S. Salehi, Varieties of Tree Languages, Ph.D. thesis, University of Turku, to be presented
in 2005.
[73] S. Salehi and M. Steinby, Varieties of many-sorted recognizable sets, TUCS Technical
Report 626, Turku Centre for Computer Science, Turku, 2004.
[74] S. Salehi and M. Steinby, Tree algebras and regular tree languages, in preparation.
[75] K. Salomaa, Syntactic monoids of regular forests, M.Sc. thesis, University of Turku,
1983, in Finnish.
Algebraic classifications of regular tree languages 431
[76] B. M. Schein, Homomorphisms and subdirect decompositions of semigroups, Pacific J.
Math. 17 (1966), 529–547.
[77] M.-P. Sch¨utzenberger, On finite monoids having only trivial subgroups, Information
and Control 8 (1965), 190–194.
[78] M. Steinby, Syntactic algebras and varieties of recognizable sets, in: LesArbresen
alg`ebre et en programmation,Universit´e de Lille, Lille, 1979, 226–240.
[79] M. Steinby, Some algebraic aspects of recognizability and rationality, Foundations of
Computing Theory, Lecture Notes in Comput. Sci. 117, Springer, Berlin, 1981, 360–372.
[80] M. Steinby, A theory of tree language varieties, in: Tree Automata and Languages (M.
Nivat and A. Podelski, eds.), North-Holland, Amsterdam, 1992, 57–81.
[81] M. Steinby, On generalizations of the Nerode and Myhill theorems, Bulletin of the
EATCS 48 (1992), 191–198.
[82] M. Steinby, Recognizable and rational subsets of algebras, Fundamenta Informaticae
18 (1993), 249–266.
[83] M. Steinby, Classifying regular languages by their syntactic algebras, in: Results and
Trends in Computer Science, Lecture Notes in Comput. Sci. 812, Springer, Berlin,
1994, 353–364.
[84] M. Steinby, General varieties of tree languages, Theoret. Comput. Sci. 205 (1998), 1–43.
[85] J. W. Thatcher and J. B. Wright, Generalized finite automata theory with an appli-
cation to a decision problem of second order logic, Mathematical Systems Theory 2
(1968), 57–81.
[86] D. Th´erien, Classification of regular congruences, Ph.D. Thesis, University of Waterloo,
1980.
[87] D. Th´erien, Classification of finite monoids: the language approach, Theoretical Com-
puter Science 14 (1981), 195–208.
[88] W. Thomas, On non-counting tree languages, Grundlagen der Theoretische Informatik
(Proc. 1. Intern. Workshop, Paderborn 1982), 234–242.
[89] W. Thomas, Logical aspects in the study of tree languages, in: 9th Colloquium on Trees
in Algebra and Programming (B. Courcelle, ed.), Cambridge University Press, London,
1984, 31–49.
[90] J. Vir´agh, Deterministic ascending tree automata I, Acta Cybernetica 5 (1980), 33–42.
[91] W. Wechler, Universal Algebra for Computer Scientists, Springer-Verlag, Berlin, 1992.
[92] T. Wilke, An algebraic characterization of frontier testable tree languages, Theoret.
Comput. Sci. 154 (1996), 85–106.
432 M. Steinby
[93] R. T. Yeh, Some structural properties of generalized automata and algebras, Mathe-
matical Systems Theory 5 (1971), 306–318.
[94] S. Yu, Regular languages, in: Handbook of Formal Languages, Vol. 1 (G. Rozenberg
and A. Salomaa, eds.), Springer-Verlag, Berlin, 1997, 41–110.
Index
Abelian algebra 280
Abelian congruence 280, 321
Abelian group 175
Abelian lattice 282
Abelian ring 282
Abelian variety 299
A-completeness 230
affine variety 299
arithmetical variety 284
agent 241, 253
Allen’s interval algebra 205
alphabet 225, 387, 391
Archimedean epigroup 343, 348, 351
automatic theorem proving 263
automaton 3, 77, 80, 215, 387
automaton function 227
behavior algebra 247, 248, 251
bisimilarity 246
center 280, 282, 307, 320
centrality 274, 278
clone of operations 318, 326
combinatorial variety 308
commutator equation 307, 309, 315
commuting operations 296
completeness 85, 93, 109, 230, 235
congruence distributive 284
congruence lattice 277
congruence modular 286
congruence regular 306
congruence relation 91
conjugacy invariant 38
constraint language 201
constraint satisfaction problem 181
cover property 340, 341
criterial system 218
Day terms 286
decidable 8
difference term 296
directed set 9
directly indecomposable algebra 274, 313
distributive lattice 173
endoprimal algebra 169
environment 242
epigroup 331
fine spectrum 150
finite automaton 387
finite basis problem 161, 166
finite monoid 163, 165
finite tree recognizer 393
finitely assembled semigroup 362
finiteness condition 361
free algrebra 56, 285, 299, 310, 311, 319
function with delay 223
Green’s relations 359
G-spectrum 318
Gumm terms 302
head insertion 260, 261
Heyting algebra 174
insertion function 256
insertion programming 263
interpret 283
inverse semigroup 26
J´onsson terms 284
Kleene algebra 174
Kleene-completeness 96
language 387
lattice equation 288, 296
lattice of congruences 277
locally finite 49
locally finite variety 62, 74, 155
logical set 83
look-ahead insertion 261
loop operation 306
l-valued logic 219
majority term 282
Maltsev class 283
Maltsev polynomial 297
Maltsev term 284
433
434
metric completeness 103
m-fold exponential 153
neutral algebra 316
nilpotency 7, 411
nilpotent algebra 274, 302, 303, 307, 319
nilpotent congruence 302
nilsemigroup 370
one-step insertion 258, 261
parallel composition 254, 261
path language 424
piecewise testable 8, 25
polymorphism 191
polynomial equivalence 294
polynomial operation 280
polyrelation 114, 119, 125, 129, 139
predicate 235
profinite semigroup 1, 10, 12
proving machine 269
pseudoidentity 19
pseudovariety 1, 6
pure 63
quotient algebra 317, 319
ranked alphabet 405
r-completeness 230
regular tree language 381
relational database
semisimple 69
sequential composition 253, 261
sequential function 79
shifting lemma 286
simple algebra 315
solvable algebra 273, 300, 302
solvable congruence 302
spectrum 149
Stone algebra 173
subdirectly irreductible 308, 315, 321
syntactic algebra 399
syntactic congruence 5, 400
syntactic equivalant 162
syntactic semigroup 5, 159, 418
tameness 27
term condition 274, 276, 278
term operation 277, 278, 297
ternary Abelian group 297
tolerance 277
trace equivalence 245
tractable algebra 196
transition semigroup 3
transition system 243, 265, 266
tree homomorphism 398
tree language 381
unary semigroup 334
uniform congruence 306
unipotency class 345, 359
valuation 48, 66
variety 47, 152
variety of epigroups 339
variety of finite algebra 404
variety of finite congruence 405
variety of tree languages 398
variety theorem 406
V-recognizable 14