×

Found 119 Documents (Results 1–100)

Non-returning finite automata with translucent letters. (English) Zbl 07800499

Bordihn, Henning (ed.) et al., Proceedings of the 12th international workshop on non-classical models of automata and applications, NCMA 2022, Debrecen, Hungary, August 26–27, 2022. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 367, 143-159 (2022).
MSC:  68-XX 03-XX
PDFBibTeX XMLCite
Full Text: Link

A characterization of the context-free languages by stateless ordered restart-delete automata. (English) Zbl 1440.68160

Chatzigeorgiou, Alexander (ed.) et al., SOFSEM 2020: theory and practice of computer science. 46th international conference on current trends in theory and practice of informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12011, 39-50 (2020).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

On h-lexicalized restarting automata. (English) Zbl 1483.68180

Csuhaj-Varjú, Erzsébet (ed.) et al., Proceedings of the 15th international conference on automata and formal languages, AFL’17, Debrecen, Hungary, September 4–6, 2017. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 252, 219-233 (2017).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: arXiv Link

On some decision problems for stateless deterministic ordered restarting automata. (English) Zbl 1390.68406

Shallit, Jeffrey (ed.) et al., Descriptional complexity of formal systems. 17th international workshop, DCFS 2015, Waterloo, ON, Canada, June 25–27, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19224-6/pbk; 978-3-319-19225-3/ebook). Lecture Notes in Computer Science 9118, 165-176 (2015).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

On CD-systems of stateless deterministic two-phase RR(1)-automata. (English) Zbl 1367.68170

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, 111-137 (2012).
MSC:  68Q45 68Q10
PDFBibTeX XMLCite
Full Text: DOI

On the descriptional complexity of the window size for deterministic restarting automata. (English) Zbl 1297.68149

Moreira, Nelma (ed.) et al., Implementation and application of automata. 17th international conference, CIAA 2012, Porto, Portugal, July 17–20, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31605-0/pbk). Lecture Notes in Computer Science 7381, 253-264 (2012).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

An automata-theoretical characterization of context-free trace languages. (English) Zbl 1298.68152

Černá, Ivana (ed.) et al., SOFSEM 2011: Theory and practice of computer science. 37th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 22–28, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-18380-5/pbk). Lecture Notes in Computer Science 6543, 406-417 (2011).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

Transductions computed by PC-systems of monotone deterministic restarting automata. (English) Zbl 1297.68138

Domaratzki, Michael (ed.) et al., Implementation and application of automata. 15th international conference, CIAA 2010, Winnipeg, MB, Canada, August 12–15, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-18097-2/pbk). Lecture Notes in Computer Science 6482, 163-172 (2011).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

On parallel communicating grammar systems and correctness preserving restarting automata. (English) Zbl 1234.68234

Dediu, Adrian Horia (ed.) et al., Language and automata theory and applications. Third international conference, LATA 2009, Tarragona, Spain, April 2–8, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00981-5/pbk). Lecture Notes in Computer Science 5457, 660-671 (2009).
MSC:  68Q45 68Q42
PDFBibTeX XMLCite
Full Text: DOI

On stateless deterministic restarting automata. (English) Zbl 1206.68116

Nielsen, Mogens (ed.) et al., SOFSEM 2009: Theory and practice of computer science. 35th conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 24–30, 2009. Proceedings. Berlin: Springer (ISBN 978-3-540-95890-1/pbk). Lecture Notes in Computer Science 5404, 353-364 (2009).
MSC:  68Q05 68Q45
PDFBibTeX XMLCite
Full Text: DOI

On alternating phrase-structure grammars. (English) Zbl 1156.68434

Martín-Vide, Carlos (ed.) et al., Language and automata theory and applications. Second international conference, LATA 2008, Tarragona, Spain, March 13–19, 2008. Revised papers. Berlin: Springer (ISBN 978-3-540-88281-7/pbk). Lecture Notes in Computer Science 5196, 397-408 (2008).
MSC:  68Q42 68Q45
PDFBibTeX XMLCite
Full Text: DOI

Restarting tree automata and linear context-free tree languages. (English) Zbl 1148.68403

Bozapalidis, Symeon (ed.) et al., Algebraic informatics. Second international conference, CAI 2007, Thessaloniki, Greece, May 21–25, 2007. Revised selected and invited papers. Berlin: Springer (ISBN 978-3-540-75413-8/pbk). Lecture Notes in Computer Science 4728, 275-289 (2007).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

FDT is undecidable for finitely presented monoids with solvable word problems. (English) Zbl 1508.20069

Chlebus, Bogdan S. (ed.) et al., Fundamentals of computation theory. 11th international symposium, FCT ’97, Jagiellonian Univ., Kraków, Poland, September 1–3, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1279, 388-399 (1997).
MSC:  20M05
PDFBibTeX XMLCite
Full Text: DOI

The word matching problem is undecidable for finite special string-rewriting systems that are confluent. (English) Zbl 1401.68138

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, 638-648 (1997).
MSC:  68Q42 03D35
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field

Software