Author name cluster

Andreas Maletti

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

2 author rows

I&C Journal 2023 Journal Article

Combinatory categorial grammars as generators of weighted forests

Andreas Maletti
Lena Katharina Schiffer

Combinatory Categorial Grammar (CCG) is an extension of categorial grammar that is well-established in computational linguistics. It is mildly context-sensitive, so it is efficiently parsable and reaches an expressiveness that is suitable for describing natural languages. Weighted CCG (wCCG) are introduced as a natural extension of CCG with weights taken from an arbitrary commutative semiring. Their expressive power is compared to other weighted formalisms with special emphasis on the weighted forests generated by wCCG since the ability to express the underlying syntactic structure of an input sentence is a vital feature of CCG in the area of natural language processing. Building on recent results for the expressivity in the unweighted setting, the corresponding results are derived for the weighted setting for any commutative semiring. More precisely, the weighted forests generatable by wCCG are also generatable by weighted simple monadic context-free tree grammar (wsCFTG). If the rule system is restricted to application rules and composition rules of first degree, then the generatable weighted forests are exactly the regular weighted forests. Finally, when only application rules are allowed, then a proper subset of the regular weighted forests is generatable.

Details DOI

I&C Journal 2023 Journal Article

Weighted two-way transducers

Fan Feng
Andreas Maletti

Weighted two-way transducers over complete commutative semirings are introduced and investigated. Their computed mappings have two-way definable support. Conversely, for every two-way definable relation R there exists a mapping that has support R and is computable by a weighted two-way transducer. The class of all such computed mappings is naturally closed under sum. Finally, both the subclass computed by deterministic weighted two-way transducers and the subclass computed by unambiguous weighted two-way transducers are shown to be closed under composition, pseudo Hadamard product, unambiguous Cauchy product, and unambiguous Kleene iteration.

Details DOI

TCS Journal 2018 Journal Article

Multiple context-free tree grammars: Lexicalization and characterization

Joost Engelfriet
Andreas Maletti
Sebastian Maneth

Multiple (simple) context-free tree grammars are investigated, where “simple” means “linear and nondeleting”. Every multiple context-free tree grammar that is finitely ambiguous can be lexicalized; i. e. , it can be transformed into an equivalent one (generating the same tree language) in which each rule of the grammar contains a lexical symbol. Due to this transformation, the rank of the nonterminals increases at most by 1, and the multiplicity (or fan-out) of the grammar increases at most by the maximal rank of the lexical symbols; in particular, the multiplicity does not increase when all lexical symbols have rank 0. Multiple context-free tree grammars have the same tree generating power as multi-component tree adjoining grammars (provided the latter can use a root-marker). Moreover, every multi-component tree adjoining grammar that is finitely ambiguous can be lexicalized. Multiple context-free tree grammars have the same string generating power as multiple context-free (string) grammars and polynomial time parsing algorithms. A tree language can be generated by a multiple context-free tree grammar if and only if it is the image of a regular tree language under a deterministic finite-copying macro tree transducer. Multiple context-free tree grammars can be used as a synchronous translation device.

Details DOI

TCS Journal 2017 Journal Article

Survey: Finite-state technology in natural language processing

Andreas Maletti

In this survey, we will discuss current uses of finite-state information in several statistical natural language processing tasks. To this end, we will review standard approaches in tokenization, part-of-speech tagging, and parsing, and illustrate the utility of finite-state information and technology in these areas. The particular problems were chosen to allow a natural progression from simple prediction to structured prediction. We aim for a sufficiently formal presentation suitable for readers with a background in automata theory that allows to appreciate the contribution of finite-state approaches, but we will not discuss practical issues outside the core ideas. We provide instructive examples and pointers into the relevant literature for all constructions. We close with an outlook on finite-state technology in statistical machine translation.

Details DOI

TCS Journal 2015 Journal Article

Hyper-optimization for deterministic tree automata

Andreas Maletti

Hyper-minimization is a lossy minimization technique that allows a finite number of errors. It was already demonstrated that hyper-minimization can be performed efficiently for deterministic string automata and (bottom-up) deterministic tree automata (DTAs). The asymptotically fastest DTA hyper-minimization algorithms run in time O ( m ⋅ log ⁡ n ), where m is the size of the DTA and n is the number of its states. In this contribution, the committed errors are investigated. First, the structure of all hyper-minimal DTAs for a given tree language is characterized, which also yields a formula for the number of such hyper-minimal DTAs. Second, an algorithm is developed that computes the number of errors that a given hyper-minimal DTA commits when compared to a given reference DTA. Third, it is shown that optimal hyper-minimization (i. e. , computing a hyper-minimal DTA that commits the least number of errors of all hyper-minimal DTAs) can be achieved in time O ( m ⋅ n ). Finally, a discussion of various other error measures (besides only their number) is provided.

Details DOI

MFCS Conference 2011 Conference Paper

On Minimising Automata with Errors

Pawel Gawrychowski
Artur Jez
Andreas Maletti

Abstract The problem of k -minimisation for a DFA M is the computation of a smallest DFA N (where the size | M | of a DFA M is the size of the domain of the transition function) such that L ( M ) Δ L ( N ) ⊆ Σ < k, which means that their recognized languages differ only on words of length less than k. The previously best algorithm, which runs in time \(\mathcal{O}(\mid M \mid{\rm log}^{2} n)\) where n is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster \(\mathcal{O}(\mid M \mid\log n)\) algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a k -minimal DFA for each k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA M and numbers k and m, it is NP-hard to decide whether there exists a k -minimal DFA N with | L ( M ) Δ L ( N ) ≤ m. A similar result holds for hyper-minimisation of DFAs in general: Given a DFA M and numbers s and m, it is NP-hard to decide whether there exists a DFA N with at most s states such that | L ( M ) Δ L ( N ) ≤ m.

Details

MFCS Conference 2011 Conference Paper

Pushing for Weighted Tree Automata

Andreas Maletti
Daniel Quernheim

Abstract Explicit pushing for weighted tree automata over semifields is introduced. A careful selection of the pushing weights allows a normalization of bottom-up deterministic weighted tree automata. Automata in the obtained normal form can be minimized by a simple transformation into an unweighted automaton followed by unweighted minimization. This generalizes results of Mohri and Eisner for deterministic weighted string automata to the tree case. Moreover, the new strategy can also be used to test equivalence of two bottom-up deterministic weighted tree automata M 1 and M 2 in time O (| M |log| Q |), where | M | = | M 1 | + | M 2 | and | Q | is the sum of the number of states of M 1 and M 2. This improves the previously best running time O (| M 1 |·| M 2 |).

Details

TCS Journal 2010 Journal Article

An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton

Markus Holzer
Andreas Maletti

We improve a recent result [A. Badr, Hyper-minimization in O ( n 2 ), Internat. J. Found. Comput. Sci. 20 (4) (2009) 735–746] for hyper-minimized finite automata. Namely, we present an O ( n log n ) algorithm that computes for a given deterministic finite automaton (dfa) an almost-equivalent dfa that is as small as possible—such an automaton is called hyper-minimal. Here two finite automata are almost-equivalent if and only if the symmetric difference of their languages is finite. In other words, two almost-equivalent automata disagree on acceptance on finitely many inputs. In this way, we solve an open problem stated in [A. Badr, V. Geffert, I. Shipman, Hyper-minimizing minimized deterministic finite state automata, RAIRO Theor. Inf. Appl. 43 (1) (2009) 69–94] and by Badr. Moreover, we show that minimization linearly reduces to hyper-minimization, which shows that the time-bound O ( n log n ) is optimal for hyper-minimization. Independently, similar results were obtained in [P. Gawrychowski, A. Jeż, Hyper-minimisation made efficient, in: Proc. 34th Int. Symp. Mathematical Foundations of Computer Science, in: LNCS, vol. 5734, Springer, 2009, pp. 356–368].

Details DOI

TCS Journal 2009 Journal Article

Backward and forward bisimulation minimization of tree automata

Johanna Högberg
Andreas Maletti
Jonathan May

We improve on an existing [P. A. Abdulla, J. Högberg, L. Kaati, Bisimulation minimization of tree automata, International Journal of Foundations of Computer Science 18(4) (2007) 699–713] bisimulation minimization algorithm for finite-state tree automata by introducing backward and forward bisimulation and developing minimization algorithms for them. Minimization via forward bisimulation is also effective on deterministic tree automata, faster than the previous algorithm, and yields the minimal equivalent deterministic tree automaton. Minimization via backward bisimulation generalizes the previous algorithm and can yield smaller automata but is just as fast. We demonstrate implementations of these algorithms on a typical task in natural language processing.

Details DOI

I&C Journal 2009 Journal Article

Minimizing deterministic weighted tree automata

Andreas Maletti

Deterministic weighted tree automata (dwta) have found promising applications as language models in Natural Language Processing. It is known that dwta over commutative semifields can be effectively minimized. An efficient algorithm for minimizing them is presented. It is polynomial-time given that all operations of the semifield including the computation of the inverses are polynomial. More precisely, if the operations can be performed in constant time, then the algorithm constructs an equivalent minimal (with respect to the number of states) dwta in time O ( lmn ) where l is the maximal rank of the input symbols, m is the number of (useful) transitions, and n is the number of states of the input dwta.

Details DOI

I&C Journal 2008 Journal Article

Compositions of extended top-down tree transducers

Andreas Maletti

Unfortunately, the class of transformations computed by linear extended top-down tree transducers with regular look-ahead is not closed under composition. It is shown that the class of transformations computed by certain linear bimorphisms coincides with the previously mentioned class. Moreover, it is demonstrated that every linear epsilon-free extended top-down tree transducer with regular look-ahead can be implemented by a linear multi bottom-up tree transducer. The class of transformations computed by the latter device is shown to be closed under composition, and to be included in the composition of the class of transformations computed by top-down tree transducers with itself. More precisely, it constitutes the composition closure of the class of transformations computed by finite-copying top-down tree transducers.

Details DOI

TCS Journal 2006 Journal Article

Compositions of tree series transformations

Andreas Maletti

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottom-up tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation.

Details DOI

TCS Journal 2005 Journal Article

HASSE diagrams for classes of deterministic bottom-up tree-to-tree-series transformations

Andreas Maletti

The relationship between classes of tree-to-tree-series and o-tree-to-tree-series transformations computed by restricted deterministic bottom-up weighted tree transducers is investigated. Essentially, these transducers are deterministic bottom-up tree series transducers, except that the former are defined over monoids whereas the latter are defined over semirings and only use the multiplicative monoid thereof. In particular, the common restrictions of nondeletion, linearity, totality, and homomorphism can equivalently be defined for deterministic bottom-up weighted tree transducers. Using well-known results of classical tree transducer theory and also new results on deterministic weighted tree transducers, classes of tree-to-tree-series and o-tree-to-tree-series transformations computed by restricted deterministic bottom-up weighted tree transducers are ordered by set inclusion. More precisely, for every commutative monoid and all sensible combinations of the above mentioned restrictions, the inclusion relation of the classes of tree-to-tree-series and o-tree-to-tree-series transformations is completely conveyed by means of Hasse diagrams.

Details DOI