×

Found 44 Documents (Results 1–44)

Finite transducers and rational transductions. (English) Zbl 1517.68195

Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 79-111 (2021).
MSC:  68Q45 68Q70
PDFBibTeX XMLCite
Full Text: DOI

Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems. (English) Zbl 07561757

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 29, 29 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Equivalence of finite-valued streaming string transducers is decidable. (English) Zbl 07561615

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 122, 15 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

The many facets of string transducers (Invited Talk). (English) Zbl 07559111

Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 2, 21 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

An optimal bound on the solution sets of one-variable word equations and its consequences. (English) Zbl 1492.68114

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 136, 13 p. (2018).
MSC:  68R15
PDFBibTeX XMLCite
Full Text: DOI

One-unknown word equations and three-unknown constant-free word equations. (English) Zbl 1436.68284

Brlek, Srečko (ed.) et al., Developments in language theory. 20th international conference, DLT 2016, Montréal, Canada, July 25–28, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9840, 332-343 (2016).
MSC:  68R15
PDFBibTeX XMLCite
Full Text: DOI

Equations in the partial semigroup of words with overlapping products. (English) Zbl 1367.68214

Bordihn, Henning (ed.) et al., Languages alive. Essays dedicated to Jürgen Dassow on the occasion of his 65th birthday. Berlin: Springer (ISBN 978-3-642-31643-2/pbk). Lecture Notes in Computer Science 7300, 99-110 (2012).
MSC:  68R15 20M35
PDFBibTeX XMLCite
Full Text: DOI

On the complexity of Hmelevskii’s theorem and satisfiability of three unknown equations. (English) Zbl 1247.68214

Diekert, Volker (ed.) et al., Developments in language theory. 13th international conference, DLT 2009, Stuttgart, Germany, June 30–July 3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02736-9/pbk). Lecture Notes in Computer Science 5583, 443-453 (2009).
MSC:  68R15 68Q25
PDFBibTeX XMLCite
Full Text: DOI

An analysis and a reproof of Hmelevskii’s theorem. (Extended abstract). (English) Zbl 1161.68706

Ito, Masami (ed.) et al., Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85779-2/pbk). Lecture Notes in Computer Science 5257, 467-478 (2008).
MSC:  68R15
PDFBibTeX XMLCite
Full Text: DOI

The expressibility of languages and relations by word equations. (English) Zbl 1401.68163

Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7–11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 98-109 (1997).
MSC:  68Q45 68R15
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field

Software