2009 | ||
---|---|---|
129 | EE | Dana Pardubská, Martin Plátek, Friedrich Otto: On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata. LATA 2009: 660-671 |
128 | EE | Martin Kutrib, Hartmut Messerschmidt, Friedrich Otto: On Stateless Deterministic Restarting Automata. SOFSEM 2009: 353-364 |
127 | EE | Hartmut Messerschmidt, Friedrich Otto: On Deterministic CD-Systems of Restarting Automata. Int. J. Found. Comput. Sci. 20(1): 185-209 (2009) |
2008 | ||
126 | Carlos Martín-Vide, Friedrich Otto, Henning Fernau: Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers Springer 2008 | |
125 | EE | Etsuro Moriya, Friedrich Otto: On Alternating Phrase-Structure Grammars. LATA 2008: 397-408 |
124 | EE | Friedrich Otto, Martin Plátek: A Two-Dimensional Taxonomy of Proper Languages of Lexicalized FRR-Automata. LATA 2008: 409-420 |
123 | EE | Hartmut Messerschmidt, Friedrich Otto: On determinism versus nondeterminism for restarting automata. Inf. Comput. 206(9-10): 1204-1218 (2008) |
122 | EE | Tomasz Jurdzinski, Friedrich Otto, Frantisek Mráz, Martin Plátek: On the Complexity of 2-Monotone Restarting Automata. Theory Comput. Syst. 42(4): 488-518 (2008) |
2007 | ||
121 | EE | Heiko Stamer, Friedrich Otto: Restarting Tree Automata and Linear Context-Free Tree Languages. CAI 2007: 275-289 |
120 | EE | Frantisek Mráz, Martin Plátek, Friedrich Otto: A Measure for the Degree of Nondeterminism of Context-Free Languages. CIAA 2007: 192-202 |
119 | EE | Hartmut Messerschmidt, Friedrich Otto: Strictly Deterministic CD-Systems of Restarting Automata. FCT 2007: 424-434 |
118 | EE | Frantisek Mráz, Friedrich Otto, Martin Plátek: Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata. MCU 2007: 230-241 |
117 | EE | Heiko Stamer, Friedrich Otto: Restarting Tree Automata. SOFSEM (1) 2007: 510-521 |
116 | EE | Etsuro Moriya, Friedrich Otto: Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata. IEICE Transactions 90-D(6): 889-894 (2007) |
115 | EE | Tomasz Jurdzinski, Friedrich Otto: Shrinking Restarting Automata. Int. J. Found. Comput. Sci. 18(2): 361-385 (2007) |
114 | EE | Hartmut Messerschmidt, Friedrich Otto: Cooperating Distributed Systems of Restarting Automata. Int. J. Found. Comput. Sci. 18(6): 1333-1342 (2007) |
2006 | ||
113 | EE | Hartmut Messerschmidt, Frantisek Mráz, Friedrich Otto, Martin Plátek: Correctness Preservation and Complexity of Simple RL-Automata. CIAA 2006: 162-172 |
112 | EE | Hartmut Messerschmidt, Friedrich Otto: On Nonforgetting Restarting Automata That Are Deterministic and/or Monotone. CSR 2006: 247-258 |
111 | EE | Frantisek Mráz, Friedrich Otto, Martin Plátek: On the Gap-Complexity of Simple RL-Automata. Developments in Language Theory 2006: 83-94 |
110 | EE | Frantisek Mráz, Friedrich Otto, Martin Plátek: Learning Analysis by Reduction from Positive Data. ICGI 2006: 125-136 |
109 | EE | Friedrich Otto: Restarting Automata. Recent Advances in Formal Languages and Applications 2006: 269-303 |
108 | EE | Tomasz Jurdzinski, Friedrich Otto: Restarting automata with restricted utilization of auxiliary symbols. Theor. Comput. Sci. 363(2): 162-181 (2006) |
107 | EE | Frantisek Mráz, Friedrich Otto, Martin Plátek, Tomasz Jurdzinski: Marcus t-contextual grammars and cut hierarchies and monotonicity for restarting automata. Theor. Comput. Sci. 366(3): 272-296 (2006) |
106 | EE | Tomasz Jurdzinski, Frantisek Mráz, Friedrich Otto, Martin Plátek: Degrees of non-monotonicity for restarting automata. Theor. Comput. Sci. 369(1-3): 1-34 (2006) |
2005 | ||
105 | EE | Tomasz Jurdzinski, Friedrich Otto: Restricting the Use of Auxiliary Symbols for Restarting Automata. CIAA 2005: 176-187 |
104 | EE | Tomasz Jurdzinski, Frantisek Mráz, Friedrich Otto, Martin Plátek: Monotone Deterministic RL-Automata Don't Need Auxiliary Symbols. Developments in Language Theory 2005: 284-295 |
103 | EE | Markus Holzer, Friedrich Otto: Shrinking Multi-pushdown Automata. FCT 2005: 305-316 |
102 | EE | Tomasz Jurdzinski, Friedrich Otto: Shrinking Restarting Automata. MFCS 2005: 532-543 |
101 | EE | Tomasz Jurdzinski, Friedrich Otto, Frantisek Mráz, Martin Plátek: Deterministic Two-Way Restarting Automata and Marcus Contextual Grammars. Fundam. Inform. 64(1-4): 217-228 (2005) |
100 | EE | Gundula Niemann, Friedrich Otto: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inf. Comput. 197(1-2): 1-21 (2005) |
99 | EE | Etsuro Moriya, Dieter Hofbauer, Maria Huber, Friedrich Otto: On state-alternating context-free grammars. Theor. Comput. Sci. 337(1-3): 183-216 (2005) |
2004 | ||
98 | EE | Tomasz Jurdzinski, Friedrich Otto, Frantisek Mráz, Martin Plátek: On the Complexity of 2-Monotone Restarting Automata. Developments in Language Theory 2004: 237-248 |
97 | EE | Tomasz Jurdzinski, Friedrich Otto, Frantisek Mráz, Martin Plátek: On Left-Monotone Deterministic Restarting Automata. Developments in Language Theory 2004: 249-260 |
96 | EE | Friedrich Otto, Olga Sokratova: Reduction relations for monoid semirings. J. Symb. Comput. 37(3): 343-376 (2004) |
95 | Friedrich Otto: Some Results on RWW- and RRWW-Automata and their Relation to the Class of Growing Context-Sensitive Languages. Journal of Automata, Languages and Combinatorics 9(4): 407-437 (2004) | |
2003 | ||
94 | EE | Friedrich Otto: Restarting Automata and Their Relations to the Chomsky Hierarchy. Developments in Language Theory 2003: 55-74 |
93 | Gundula Niemann, Friedrich Otto: Church-Rosser Languages and Their Relationship to Other Language Classes. Grammars and Automata for String Processing 2003: 295-304 | |
92 | EE | Masashi Katsura, Yuji Kobayashi, Friedrich Otto: Undecidable properties of monoids with word problem solvable in linear time. Part II-- cross sections and homological and homotopical finiteness conditions. Theor. Comput. Sci. 1-3(301): 79-101 (2003) |
91 | Martin Beaudry, Markus Holzer, Gundula Niemann, Friedrich Otto: McNaughton families of languages. Theor. Comput. Sci. 290(3): 1581-1628 (2003) | |
2002 | ||
90 | EE | Yuji Kobayashi, Friedrich Otto: Some Exact Sequences for The Homotopy (Bi-)Module af A Monoid. IJAC 12(1-2): 247-283 (2002) |
89 | Robert Cremanns, Friedrich Otto: A Completion Procedure for Finitely Presented Groups That Is Based on Word Cycles. J. Autom. Reasoning 28(3): 235-256 (2002) | |
2001 | ||
88 | EE | Martin Beaudry, Markus Holzer, Gundula Niemann, Friedrich Otto: On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy. Developments in Language Theory 2001: 340-348 |
87 | Gundula Niemann, Friedrich Otto: On the Power of RRWW-Automata. Words, Semigroups, and Transductions 2001: 341-355 | |
86 | EE | Yuji Kobayashi, Friedrich Otto: On Homotopical and Homological Finiteness Conditions for Finitely Presented Monoids. IJAC 11(3): 391-403 (2001) |
85 | Friedrich Otto, Nikola Ruskuc: Confluent Monadic String-Rewriting Systems and Automatic Structures. Journal of Automata, Languages and Combinatorics 6(3): 375-388 (2001) | |
2000 | ||
84 | EE | Masashi Katsura, Yuji Kobayashi, Friedrich Otto: Undecidability Results for Monoids with Linear-Time Decidable Word Problems. ISAAC 2000: 278-289 |
83 | Gundula Niemann, Friedrich Otto: Confluent Internal Contextual Languages. Recent Topics in Mathematical and Computational Linguistics 2000: 234-244 | |
82 | EE | Friedrich Otto, Andrea Sattler-Klein: The Property Fdt is Undecidable for Finitely Presented Monoids that Have Polynomial-Time Decidable Word Problems. IJAC 10(3): 285-308 (2000) |
81 | Friedrich Otto: On Dehn Functions of Finitely Presented Bi-Automatic Monoids. Journal of Automata, Languages and Combinatorics 5(4): 405-420 (2000) | |
80 | EE | Yuji Kobayashi, Friedrich Otto: Repetitiveness of languages generated by morphisms. Theor. Comput. Sci. 240(2): 337-378 (2000) |
1999 | ||
79 | EE | Friedrich Otto: On S-Regular Prefix-Rewriting Systems and Automatic Structures. COCOON 1999: 422-431 |
78 | Gundula Niemann, Friedrich Otto: Restarting automata, Church-Rosser languages, and representations of r.e. languages. Developments in Language Theory 1999: 103-114 | |
77 | EE | Friedrich Otto: On the Connections between Rewriting and Formal Language Theory. RTA 1999: 332-355 |
1998 | ||
76 | EE | Gundula Niemann, Friedrich Otto: The Church-Rosser Languages Are the Deterministic Variants of the Growing Context-Sensitive Languages. FoSSaCS 1998: 243-257 |
75 | EE | Friedrich Otto, Andrea Sattler-Klein, Klaus Madlener: Automatic Monoids Versus Monoids with Finite Convergent Presentations. RTA 1998: 32-46 |
74 | Gerhard Buntrock, Friedrich Otto: Growing Context-Sensitive Languages and Church-Rosser Languages. Inf. Comput. 141(1): 1-36 (1998) | |
73 | Friedrich Otto, Masashi Katsura, Yuji Kobayashi: Infinite Convergent String-Rewriting Systems and Cross-Sections for Finitely Presented Monoids. J. Symb. Comput. 26(5): 621-648 (1998) | |
72 | EE | Friedrich Otto, Paliath Narendran, Daniel J. Dougherty: Equational Unification, Word Unification, and 2nd-Order Equational Unification. Theor. Comput. Sci. 198(1-2): 1-47 (1998) |
71 | EE | Friedrich Otto: Some Undecidability Results Concerning the Property of Preserving Regularity. Theor. Comput. Sci. 207(1): 43-72 (1998) |
1997 | ||
70 | Friedrich Otto, Yuji Kobayashi: Properties of Monoids That Are Presented by Finite Convergent String-Rewriting Systems - A Survey. Advances in Algorithms, Languages, and Complexity 1997: 225-266 | |
69 | Yuji Kobayashi, Friedrich Otto, Patrice Séébold: A Complete Characterization of Repetitive Morphisms over the Two-Letter Alphabet. COCOON 1997: 393-402 | |
68 | Friedrich Otto, Andrea Sattler-Klein: FDT is Undecidable for Finitely Presented Monoids with Solvable Word Problems. FCT 1997: 388-399 | |
67 | Paliath Narendran, Friedrich Otto: The Word Matching Problem Is Undecidable For Finite Special String-Rewriting Systems That Are Confluent. ICALP 1997: 638-648 | |
66 | Yuji Kobayashi, Friedrich Otto: Repetitiveness of D0L-Languages Is Decidable in Polynomial Time. MFCS 1997: 337-346 | |
65 | Friedrich Otto, Masashi Katsura, Yuji Kobayashi: Cross-Sections for Finitely Presented Monoids with Decidable Word Problems. RTA 1997: 53-67 | |
64 | Friedrich Otto: On the Property of Preserving Regularity for String-Rewriting Systems. RTA 1997: 83-97 | |
63 | Klaus Madlener, Friedrich Otto: Some Undecidability Results for Finitely Generated Thue Congruences on aTwo-Letter Alphabet. Fundam. Inform. 30(1): 31-44 (1997) | |
62 | Paliath Narendran, Friedrich Otto: Single Versus Simultaneous Equational Unification and Equational Unification for Variable-Permuting Theories. J. Autom. Reasoning 19(1): 87-115 (1997) | |
1996 | ||
61 | Robert Cremanns, Friedrich Otto: For Groups the Property of Having Finite Derivation Type is Equivalent to the Homological Finiteness Condition FP_3. J. Symb. Comput. 22(2): 155-177 (1996) | |
1995 | ||
60 | Friedrich Otto, Paliath Narendran, Daniel J. Dougherty: Some Independent Results for Equational Unification. RTA 1995: 367-381 | |
59 | Gerhard Buntrock, Friedrich Otto: Growing Context-Sensitive Languages and Church-Rosser Languages. STACS 1995: 313-324 | |
58 | EE | Friedrich Otto: Solvability of Word Equations Modulo Finite Special and Confluent String-Rewriting Systems is Undecidable in General. Inf. Process. Lett. 53(5): 237-242 (1995) |
57 | Friedrich Otto: On Confluence Versus Strong Confluence for One-Rule Trace-Rewriting Systems. Mathematical Systems Theory 28(4): 363-384 (1995) | |
1994 | ||
56 | EE | Robert Cremanns, Friedrich Otto: Constructing Canonical Presentations for Subgroups of Context-Free Groups in Polynomial Time (extended abstract). ISSAC 1994: 147-153 |
55 | Norbert Kuhn, Klaus Madlener, Friedrich Otto: Computing Presentations for Subgroups of Polycyclic Groups and of Context-Free Groups. Appl. Algebra Eng. Commun. Comput. 5: 287-316 (1994) | |
54 | Robert Cremanns, Friedrich Otto: Finite Derivation Type Implies the Homological Finiteness Condition FP_3. J. Symb. Comput. 18(2): 91-112 (1994) | |
53 | Craig C. Squier, Friedrich Otto, Yuji Kobayashi: A Finiteness Condition for Rewriting Systems. Theor. Comput. Sci. 131(2): 271-294 (1994) | |
52 | Friedrich Otto, Paliath Narendran: Codes Modulo Finite Monadic String-Rewriting Systems. Theor. Comput. Sci. 134(1): 175-188 (1994) | |
1993 | ||
51 | Klaus Madlener, Andrea Sattler-Klein, Friedrich Otto: On the Problem of Generating Small Convergent Systems. J. Symb. Comput. 16(2): 167-187 (1993) | |
50 | Friedrich Otto, Daniel E. Cohen, Klaus Madlener: Separating the Intrinsic Complexity and the Derivational complexity of the Word Problem for Finitely Presented Groups. Math. Log. Q. 39: 143-157 (1993) | |
49 | Klaus Madlener, Paliath Narendran, Friedrich Otto, Louxin Zhang: On Weakly Confluent Monadic String-Rewriting Systems. Theor. Comput. Sci. 113(1): 119-165 (1993) | |
1992 | ||
48 | Klaus Madlener, Friedrich Otto, Andrea Sattler-Klein: Generating Small Convergent Systems Can Be Extremely Hard. ISAAC 1992: 299-308 | |
47 | EE | Norbert Kuhn, Klaus Madlener, Friedrich Otto: Computing Presentations for Subgroups of Context-Free Groups. ISSAC 1992: 240-250 |
46 | Celia Wrathall, Volker Diekert, Friedrich Otto: One-Rule Trace-Rewriting Systems and Confluence. MFCS 1992: 511-521 | |
45 | Friedrich Otto: The Problem of Deciding Confluence on a Given Congruence Class is Tractable for Finite Special String-Rewriting Systems. Mathematical Systems Theory 25(4): 241-251 (1992) | |
1991 | ||
44 | Friedrich Otto: Some Undecidability Results for Weakly Confluent Monadic String-Rewriting Systems. AAECC 1991: 292-303 | |
43 | Klaus Madlener, Paliath Narendran, Friedrich Otto: A Specialized Completion Procedure for Monadic String-Rewriting Systems Presenting Groups. ICALP 1991: 279-290 | |
42 | Klaus Madlener, Friedrich Otto: Decidable Sentences for Context-Free Groups. STACS 1991: 160-171 | |
41 | Friedrich Otto, Louxin Zhang: Decision Problems for Finite Special String-Rewriting Systems that are Confluent on Some Congruence Class. Acta Inf. 28(5): 477 (1991) | |
40 | Friedrich Otto: Completing a Finite Special String-Rewriting System on the Congruence Class of the Empty Word. Appl. Algebra Eng. Commun. Comput. 2: 257-274 (1991) | |
39 | EE | Paliath Narendran, Colm Ó'Dúnlaing, Friedrich Otto: It is undecidable whether a finite special string-rewriting system presents a group. Discrete Mathematics 98(2): 153-159 (1991) |
38 | Friedrich Otto, Celia Wrathall: Overlaps in Free Partially Commutative Monoids. J. Comput. Syst. Sci. 42(2): 186-198 (1991) | |
37 | Friedrich Otto: When is an Extension of a Specification Consistent? Decidable and Undecidable Cases. J. Symb. Comput. 12(3): 255-274 (1991) | |
1990 | ||
36 | Paliath Narendran, Friedrich Otto: Some Results on Equational Unification. CADE 1990: 276-291 | |
35 | EE | Norbert Kuhn, Klaus Madlener, Friedrich Otto: A Test for lambda-Confluence for Certain Prefix Rewriting Systems with Applications to the Generalized Word Problem. ISSAC 1990: 8-15 |
34 | Deepak Kapur, Paliath Narendran, Friedrich Otto: On Ground-Confluence of Term Rewriting Systems Inf. Comput. 86(1): 14-31 (1990) | |
1989 | ||
33 | Friedrich Otto: Restrictions of Congruence Generated by Finite Canonical String-Rewriting Systems. RTA 1989: 359-370 | |
32 | Friedrich Otto: On Deciding Confluence of Finite String-Rewriting Systems Modulo Partial Commutativity. Theor. Comput. Sci. 67(1): 19-35 (1989) | |
31 | Klaus Madlener, Friedrich Otto: About the Descriptive Power of Certain Classes of Finite String-Rewriting Systems. Theor. Comput. Sci. 67(2&3): 143-172 (1989) | |
30 | Paliath Narendran, Friedrich Otto: Some Polynomial-Time Algorithms for Finite Monadic Church-Rosser Thue Systems. Theor. Comput. Sci. 68(3): 319-332 (1989) | |
1988 | ||
29 | Paliath Narendran, Friedrich Otto: Elements of Finite Order for Finite Weight-Reducing and Confluent Thue Systems. Acta Inf. 25(5): 573-591 (1988) | |
28 | EE | Friedrich Otto: An example of a one-relator group that is not a one-relation monoid. Discrete Mathematics 69(1): 101-103 (1988) |
27 | Klaus Madlener, Friedrich Otto: Commutativity in Groups Presented By Finite Church-Rosser Thue Systems. ITA 22(1): 93-111 (1988) | |
26 | Paliath Narendran, Friedrich Otto: Preperfectness is Undecidable for Thue Systems Containing Only Length-Reducing Rules and a Single Commutation Rule. Inf. Process. Lett. 29(3): 125-130 (1988) | |
25 | EE | Robert McNaughton, Paliath Narendran, Friedrich Otto: Church-Rosser Thue systems and formal languages. J. ACM 35(2): 324-344 (1988) |
24 | Klaus Madlener, Friedrich Otto: Pseudo-Natural Algorithms for Finitely Generated Presentations of Monoids and Groups. J. Symb. Comput. 5(3): 339-358 (1988) | |
1987 | ||
23 | Paliath Narendran, Friedrich Otto: It is Decidable in Polynomial Time Whether a Monoid Presented by a Finite Weight-Reducing and Confluent Thue System is Torsion-Free. AAECC 1987: 341-349 | |
22 | Klaus Madlener, Friedrich Otto: Groups Presented by Certain Classes of Finite Length-Reducing String-Rewriting Systems. RTA 1987: 133-144 | |
21 | Friedrich Otto: Some Results about Confluence on a Given Congruence Class. RTA 1987: 145-155 | |
20 | Craig C. Squier, Friedrich Otto: Th Word Problem for Finitely Presented Monoids and Finite Canonical Rewriting Systems. RTA 1987: 74-82 | |
19 | Klaus Madlener, Friedrich Otto: Using String-Rewriting for Solving the Word Problem for Finitely Presented Groups. Inf. Process. Lett. 24(5): 281-284 (1987) | |
18 | Friedrich Otto: On Deciding the Confluence of a Finite String-Rewriting System on a Given Congruence Class. J. Comput. Syst. Sci. 35(3): 285-310 (1987) | |
17 | Friedrich Otto: Finite Canonical Rewriting Systems for Congruences Generated by Concurrency Relations. Mathematical Systems Theory 20(4): 253-260 (1987) | |
1986 | ||
16 | Friedrich Otto: On Deciding Whether a Monoid is a Free Monoid or is a Group. Acta Inf. 23(1): 99-110 (1986) | |
15 | Friedrich Otto: Church-Rosser Thue Systems that Present Free Monoids. SIAM J. Comput. 15(3): 786-792 (1986) | |
14 | Friedrich Otto: The Undecidability of Self-Embedding for Finite Semi-Thue and Thue Systems. Theor. Comput. Sci. 47(3): 225-232 (1986) | |
13 | Paliath Narendran, Friedrich Otto: The Problems of Cyclic Equality and Conjugacy for Finite Complete Rewriting Systems. Theor. Comput. Sci. 47(3): 27-38 (1986) | |
1985 | ||
12 | EE | Ronald V. Book, Friedrich Otto: The Verifiability of Two-Party Protocols. EUROCRYPT 1985: 254-260 |
11 | Friedrich Otto: Deciding Algebraic Properties of Monoids Presented by Finite Church-Rosser Thue Systems. RTA 1985: 95-106 | |
10 | Ronald V. Book, Friedrich Otto: Cancellation Rules and Extended Word Problems. Inf. Process. Lett. 20(1): 5-11 (1985) | |
9 | Klaus Madlener, Friedrich Otto: Pseudo-Natural Algorithms for the Word Problem for Finitely Presented Monoids and Groups. J. Symb. Comput. 1(4): 383-418 (1985) | |
8 | Friedrich Otto, Celia Wrathall: A Note on Thue Systems with a Single Defining Relation. Mathematical Systems Theory 18(2): 135-143 (1985) | |
7 | Paliath Narendran, Friedrich Otto: Complexity Results on the Conjugacy Problem for Monoids. Theor. Comput. Sci. 35: 227-243 (1985) | |
6 | Ronald V. Book, Friedrich Otto: On the Security of Name-Stamp Protocols. Theor. Comput. Sci. 39: 319-325 (1985) | |
5 | Ronald V. Book, Friedrich Otto: On the Verifiability of Two-Party Algebraic Protocols. Theor. Comput. Sci. 40: 101-130 (1985) | |
1984 | ||
4 | G. Bauer, Friedrich Otto: Finite Complete Rewriting Systems and the Complexity of the Word Problem. Acta Inf. 21: 521-540 (1984) | |
3 | Paliath Narendran, Friedrich Otto, Karl Winklmann: The Uniform Conjugacy Problem for Finite Church-Rosser Thue Systems is NP-Complete Information and Control 63(1/2): 58-66 (1984) | |
2 | Friedrich Otto: Finite Complete Rewriting Systems for the Jantzen Monoid and the Greendlinger Group. Theor. Comput. Sci. 32: 249-260 (1984) | |
1 | Friedrich Otto: Some Undecidability Results for Non-Monadic Church-Rosser Thue Systems. Theor. Comput. Sci. 33: 261-278 (1984) |