Andreas Maletti
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Andreas Maletti has a total of 16 co-authors. Here are the top co-authors by number of shared publications:
- Andreea-Teodora Nász
Universität Leipzig
3 shared publications - Lena Katharina Schiffer
Institute for Computer Science, Universität Leipzig, P.O. box 100 920, D-04009 Leipzig, Germany
3 shared publications - Zoltán Fülöp
University of Szeged
3 shared publications - Fan Feng
Faculty of Mathematics and Computer Science, Universität Leipzig, P.O. box 100920, 04009 Leipzig, Germany
2 shared publications Joost Engelfriet
2 shared publications- Heiko Vogler
Technische Universität Dresden
1 shared publication
Latest Publications
- 7 November 2024
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- p. 1-22
A Generalized Pumping Lemma for Weighted Recognizable Languages
Pumping lemmata are the main tool to prove that a certain language does not belong to a class of languages like the recognizable languages or the context-free languages. Essentially two pumping lemmata exist for the recognizable weighted languages: the classical one for the Boolean semiring (i.e., the unweighted case) and a similar one for fields. A joint generalization of these two pumping lemmata is provided that applies to all (right) Artinian semirings. These are (potentially non-commutative) semirings over which all finitely generated (right) semimodules have a finite bound on the length of chains of strictly increasing (right) subsemimodules. Since Artinian rings are exactly those that satisfy the Descending Chain Condition, the Artinian semirings include all skew fields and naturally also all finite semirings. The new pumping lemma thus covers most previously known pumping lemmata for recognizable weighted languages and a non-exhaustive list of semirings to which the new pumping lemma can be applied is provided as well.
- 7 November 2024
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- p. 1-22
A Generalized Pumping Lemma for Weighted Recognizable Languages
Pumping lemmata are the main tool to prove that a certain language does not belong to a class of languages like the recognizable languages or the context-free languages. Essentially two pumping lemmata exist for the recognizable weighted languages: the classical one for the Boolean semiring (i.e., the unweighted case) and a similar one for fields. A joint generalization of these two pumping lemmata is provided that applies to all (right) Artinian semirings. These are (potentially non-commutative) semirings over which all finitely generated (right) semimodules have a finite bound on the length of chains of strictly increasing (right) subsemimodules. Since Artinian rings are exactly those that satisfy the Descending Chain Condition, the Artinian semirings include all skew fields and naturally also all finite semirings. The new pumping lemma thus covers most previously known pumping lemmata for recognizable weighted languages and a non-exhaustive list of semirings to which the new pumping lemma can be applied is provided as well.
- Open Access
- 3 October 2023
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (1) , 1-28
Weighted Tree Automata with Constraints
The HOM problem, which asks whether the image of a regular tree language under a given tree homomorphism is again regular, is known to be decidable [Godoy & Giménez: The HOM problem is decidable. JACM 60(4), 2013]. However, the problem remains open for regular weighted tree languages. It is demonstrated that the main notion used in the unweighted setting, the tree automaton with equality and inequality constraints , can straightforwardly be generalized to the weighted setting and can represent the image of any regular weighted tree language under any nondeleting and nonerasing tree homomorphism. Several closure properties as well as decision problems are also investigated for the weighted tree languages generated by weighted tree automata with constraints.
- 3 October 2023
- Published by Springer Nature in Theory of Computing Systems
- Vol. 68 (1) , 1-28
Open AccessWeighted Tree Automata with Constraints
The HOM problem, which asks whether the image of a regular tree language under a given tree homomorphism is again regular, is known to be decidable [Godoy & Giménez: The HOM problem is decidable. JACM 60(4), 2013]. However, the problem remains open for regular weighted tree languages. It is demonstrated that the main notion used in the unweighted setting, the tree automaton with equality and inequality constraints , can straightforwardly be generalized to the weighted setting and can represent the image of any regular weighted tree language under any nondeleting and nonerasing tree homomorphism. Several closure properties as well as decision problems are also investigated for the weighted tree languages generated by weighted tree automata with constraints.
- 22 September 2023
- Published by Elsevier in Information and Computation
- Vol. 295
Weighted two-way transducers
- 22 September 2023
- Published by Elsevier in Information and Computation
- Vol. 295
Weighted two-way transducers
- Open Access
- 3 September 2023
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 386, 155-169
Pumping Lemmata for Recognizable Weighted Languages over Artinian Semirings
Pumping lemmata are the main tool to prove that a certain language does not belong to a class of languages like the recognizable languages or the context-free languages. Essentially two pumping lemmata exist for the recognizable weighted languages: the classical one for the BOOLEAN semiring (i.e., the unweighted case), which can be generalized to zero-sum free semirings, and the one for fields. A joint generalization of these two pumping lemmata is provided that applies to all AR-TINIAN semirings, over which all finitely generated semimodules have a finite bound on the length of chains of strictly increasing subsemimodules. Since ARTINIAN rings are exactly those that satisfy the Descending Chain Condition, the ARTINIAN semirings include all fields and naturally also all finite semirings (like the BOOLEAN semiring). The new pumping lemma thus covers most previously known pumping lemmata for recognizable weighted languages.
- 3 September 2023
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 386, 155-169
Open AccessPumping Lemmata for Recognizable Weighted Languages over Artinian Semirings
Pumping lemmata are the main tool to prove that a certain language does not belong to a class of languages like the recognizable languages or the context-free languages. Essentially two pumping lemmata exist for the recognizable weighted languages: the classical one for the BOOLEAN semiring (i.e., the unweighted case), which can be generalized to zero-sum free semirings, and the one for fields. A joint generalization of these two pumping lemmata is provided that applies to all AR-TINIAN semirings, over which all finitely generated semimodules have a finite bound on the length of chains of strictly increasing subsemimodules. Since ARTINIAN rings are exactly those that satisfy the Descending Chain Condition, the ARTINIAN semirings include all fields and naturally also all finite semirings (like the BOOLEAN semiring). The new pumping lemma thus covers most previously known pumping lemmata for recognizable weighted languages.
- 10 August 2023
- Published by Springer Nature
- p. 218-229
Weighted Bottom-Up and Top-Down Tree Transformations Are Incomparable
- 10 August 2023
- Published by Springer Nature
- p. 218-229
Weighted Bottom-Up and Top-Down Tree Transformations Are Incomparable
- 25 July 2023
- Published by Elsevier in Information and Computation
- Vol. 294
Combinatory categorial grammars as generators of weighted forests
- 25 July 2023
- Published by Elsevier in Information and Computation
- Vol. 294
Combinatory categorial grammars as generators of weighted forests
- 9 November 2022
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 34 (06) , 539-558
Compositions with Constant Weighted Extended Tree Transducers
Conjecture 11 of [Lagoutte, Maletti: Survey — Weighted extended top-down tree transducers — Part III: Composition. Proc. AFCS, LNCS 7020, p. 272–308, Springer 2011] is confirmed. It is demonstrated that the composition of a constant weighted extended tree transducer with a linear weighted top-down tree transducer can be computed by a single weighted extended tree transducer. Whereas linearity and the top-down property are syntactic, the constant property is semantic. The decidability of the constant property is investigated in several restricted settings.
- 9 November 2022
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 34 (06) , 539-558
Compositions with Constant Weighted Extended Tree Transducers
Conjecture 11 of [Lagoutte, Maletti: Survey — Weighted extended top-down tree transducers — Part III: Composition. Proc. AFCS, LNCS 7020, p. 272–308, Springer 2011] is confirmed. It is demonstrated that the composition of a constant weighted extended tree transducer with a linear weighted top-down tree transducer can be computed by a single weighted extended tree transducer. Whereas linearity and the top-down property are syntactic, the constant property is semantic. The decidability of the constant property is investigated in several restricted settings.
- Open Access
- 1 March 2022
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 124, 214-233
The tree-generative capacity of combinatory categorial grammars
- 1 March 2022
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 124, 214-233
Open AccessThe tree-generative capacity of combinatory categorial grammars